Polygon guarding with orientation

Pratap Tokekar, Volkan Isler

Research output: Contribution to journalArticlepeer-review

Abstract

The art gallery problem is a classical sensor placement problem that asks for the minimum number of guards required to see every point in an environment. The standard formulation does not take into account self-occlusions caused by a person or an object within the environment. Obtaining good views of an object from all orientations despite self-occlusions is an important requirement for surveillance and visual inspection applications. We study the art gallery problem under a constraint, termed △-guarding, that ensures that all sides of any convex object are always visible in spite of self-occlusion. Our contributions in this paper are three-fold: We first prove that Ω(n) guards are always necessary for △-guarding the interior of a simple polygon having n vertices. Second, we present a O(log⁡copt) factor approximation algorithm for △-guarding polygons with or without holes, when the guards are restricted to vertices of the polygon. Here, copt is the optimal number of guards. Third, we study the problem of △-guarding a set of line segments connecting points on the boundary of the polygon. This is motivated by applications where an object or person of interest can only move along certain paths in the polygon. We present a constant factor approximation algorithm for this problem – one of the few such results for art gallery problems.

Original languageEnglish (US)
Pages (from-to)97-109
Number of pages13
JournalComputational Geometry: Theory and Applications
Volume58
DOIs
StatePublished - Oct 1 2016

Bibliographical note

Funding Information:
P. Tokekar is supported in part by National Science Foundation grant # 1566247 . V. Isler is supported in part by the National Science Foundation grants # 1525045 , # 1317788 , and USDA NIFA MIN-98-G02 . We thank the anonymous reviewers for their helpful feedback.

Keywords

  • Art gallery problem
  • Polygon guarding
  • Visibility

Fingerprint Dive into the research topics of 'Polygon guarding with orientation'. Together they form a unique fingerprint.

Cite this