DROPS

Document

DOI: 10.4230/LIPIcs.SOCG.2015.421

Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries

Authors: Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek, and Max Willert

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

The chromatic art gallery problem asks for the minimum number of "colors" t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility - two points p and q are mutually visible if the smallest axis-aligned rectangle containing them lies within the polygon. Our main result establishes that for a conflict-free guarding of an orthogonal n-gon, in which at least one of the colors seen by every point is unique, the number of colors is Theta(loglog n). By contrast, the best upper bound for orthogonal polygons under standard (non-orthogonal) visibility is O(log n) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is Theta(log n). Finally, our techniques also help us establish the first non-trivial lower bound of Omega(loglog n / logloglog n) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.

Cite as

Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek, and Max Willert. Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 421-435, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hoffmann_et_al:LIPIcs.SOCG.2015.421,
  author =	{Hoffmann, Frank and Kriegel, Klaus and Suri, Subhash and Verbeek, Kevin and Willert, Max},
  title =	{{Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{421--435},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.421},
  URN =		{urn:nbn:de:0030-drops-50970},
  doi =		{10.4230/LIPIcs.SOCG.2015.421},
  annote =	{Keywords: Orthogonal polygons, art gallery problem, hypergraph coloring}
}

Search Results

Documents authored by Hoffmann, Frank

Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art Galleries

Abstract

Cite as

Thanks for your feedback!

Could not send message