Polygon Guarding with Orientation

Tokekar, Pratap
2014-01-03
Thumbnail Image

View/Download File

14-001.pdf (1.05 MB)

Persistent link to this item

https://hdl.handle.net/11299/215938
Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Polygon Guarding with Orientation

Authors

Published Date

2014-01-03

Publisher

Type

Report

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 a good view of an object from all orientations is viewed as an important requirement for surveillance and visual tracking applications. We study the art gallery problem under a constraint, termed triangle-guarding, that ensures that all sides of any convex object are always visible in spite of self-occlusion. Our contributions in this paper are two-fold: we first prove that $Omega(sqrt{n})$ guards are always necessary for triangle-guarding the interior of a simple polygon having n vertices. Next, we study the problem of triangle-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.

Keywords

Description

Related to

Replaces

License

Collections

Computer Science & Engineering (CS&E) Technical Reports

Series/Report Number

Technical Report; 14-001

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Tokekar, Pratap. (2014). Polygon Guarding with Orientation. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215938.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.