Tight bounds for conflict-free chromatic guarding of orthogonal art galleries

F. Hoffmann, K. Kriegel, S. Suri, K.A.B. Verbeek, M. Willert

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)
127 Downloads (Pure)


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 axisaligned 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 φ(log log 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 φ(log n). Finally, our techniques also help us establish the first non-trivial lower bound of ω(log log n/ log log log n) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.

Original languageEnglish
Title of host publication31st International Symposium on Computational Geometry, SoCG 2015, 22-25 June 2015, Eindhoven, The Netherlands
EditorsL. Arge, J. Pach
Place of Publications.l.
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages15
ISBN (Electronic)9783939897835
Publication statusPublished - 1 Jun 2015
Event31st International Symposium on Computational Geometry (SoCG 2015) - Eindhoven, Netherlands
Duration: 22 Jun 201525 Jun 2015
Conference number: 31

Publication series

NameLeibniz International Proceedings in Informatics


Workshop31st International Symposium on Computational Geometry (SoCG 2015)
Abbreviated titleSoCG 2015
Internet address


  • Art gallery problem
  • Hypergraph coloring
  • Orthogonal polygons


Dive into the research topics of 'Tight bounds for conflict-free chromatic guarding of orthogonal art galleries'. Together they form a unique fingerprint.

Cite this