Universal guard problems

DOI10.4230/LIPICS.ISAAC.2016.32MaRDI QIDQ4636515zbMATH OpenOpenAlexFDO

Authors Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, Christian Scheffer

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1611.08315

zbMATH Keywords

art gallery problempolygonizationrobust coveringuniversal guardingworst-case bounds

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points ("guards") that are "universal" in their ability to guard any of a set of possible polygonal domains in the plane. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.

Recommendations

• Universal guard problems
• Guards, Galleries, Fortresses, and the Octoplex
• Edge guards for the fortress problem
• Art gallery theorems for guarded guards.
• THE TWO GUARDS PROBLEM

Cited in

(1)

• Universal guard problems

This page was built for publication: Universal guard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636515)