Polygon guarding with orientation

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 is important for surveillance and visual tracking 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 two-fold: we first prove that Ω(√n) guards are always necessary for Δ-guarding the interior of a simple polygon having n vertices. Next, 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.

• Publication year

  2014

• Venue

  IEEE International Conference on Robotics and Automation

• Publication date

  2014-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.comgeo.2016.07.004
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Vertex Guarding in Weak Visibility Polygons

  2014cited by this paper
• A Review of Mobile Robotic Telepresence

  2013cited by this paper
• Improved Approximation for Guarding Simple Galleries from the Perimeter

  2010cited by this paper
• Approximation algorithms for art gallery problems in polygons

  2010cited by this paper
• Approximation algorithms for two optimal location problems in sensor networks

  2005cited by this paper
• Approximate Guarding of Monotone and Rectilinear Polygons

  2005cited by this paper
• Triangle Guarding

  2003influential reference
• Guarding galleries and terrains

  2002cited by this paper
• Art Gallery and Illumination Problems

  2000cited by this paper
• An efficient algorithm for guard placement in polygons with holes

  1995cited by this paper
• Almost optimal set covers in finite VC-dimension

  1995cited by this paper
• The art gallery theorem for polygons with holes

  1991cited by this paper
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph

  1988influential reference
• Art gallery theorems and algorithms

  1987cited by this paper
• Some NP-hard polygon decomposition problems

  1983cited by this paper
• A combinatorial theorem in plane geometry

  1975cited by this paper

• Localization of Partially Hidden Moving Targets Using a Fleet of UAVs via Bounded-Error Estimation

  2023cites this paper
• A Minimax Tree Based Approach for Minimizing Detectability and Maximizing Visibility

  2018cites this paper
• Argus: Realistic Target Coverage by Drones

  2017cites this paper
• Visibility-Based Target-Tracking Game: Bounds and Tracking Strategies

  2017cites this paper
• Automatic large-scale three dimensional modeling using cooperative multiple robots

  2017cites this paper
• Near-optimal probabilistic search using spatial Fourier sparse set

  2017cites this paper
• On Realistic Target Coverage by Autonomous Drones

  2017cites this paper
• GUARDING OF ORTHOGONAL POLYGONS

  2016cites this paper
• Partitioning Strategies and Task Allocation for Target-tracking with Multiple Guards in Polygonal Environments

  2016cites this paper
• Placement and motion planning algorithms for robotic sensing systems

  2014cites this paper