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: Contribution to journalArticleAcademicpeer-review

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 in the worst case Θ(log log n). By contrast, the best known 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, again in the worst case, Θ(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
Pages (from-to)24-34
JournalComputational Geometry
Volume73
DOIs
Publication statusPublished - 1 Aug 2018

Fingerprint

Color
Orthogonal Polygons
Visibility
Polygon
Art Gallery Problem
n-gon
Simple Polygon
Conflict
Art
Tableau
Rectangle
Entire
Lower bound
Upper bound
Standards

Keywords

  • Art gallery problem
  • Hypergraph coloring
  • Orthogonal polygons

Cite this

Hoffmann, F. ; Kriegel, K. ; Suri, S. ; Verbeek, K.A.B. ; Willert, M. / Tight bounds for conflict-free chromatic guarding of orthogonal art galleries. In: Computational Geometry. 2018 ; Vol. 73. pp. 24-34.
@article{bf75a5781a8e45b4904be4df84f8ecb3,
title = "Tight bounds for conflict-free chromatic guarding of orthogonal art galleries",
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 in the worst case Θ(log log n). By contrast, the best known 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, again in the worst case, Θ(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.",
keywords = "Art gallery problem, Hypergraph coloring, Orthogonal polygons",
author = "F. Hoffmann and K. Kriegel and S. Suri and K.A.B. Verbeek and M. Willert",
year = "2018",
month = "8",
day = "1",
doi = "10.1016/j.comgeo.2018.01.003",
language = "English",
volume = "73",
pages = "24--34",
journal = "Computational Geometry",
issn = "0925-7721",
publisher = "Elsevier",

}

Tight bounds for conflict-free chromatic guarding of orthogonal art galleries. / Hoffmann, F.; Kriegel, K.; Suri, S.; Verbeek, K.A.B.; Willert, M.

In: Computational Geometry, Vol. 73, 01.08.2018, p. 24-34.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Hoffmann, F.

AU - Kriegel, K.

AU - Suri, S.

AU - Verbeek, K.A.B.

AU - Willert, M.

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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 in the worst case Θ(log log n). By contrast, the best known 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, again in the worst case, Θ(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.

AB - 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 in the worst case Θ(log log n). By contrast, the best known 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, again in the worst case, Θ(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.

KW - Art gallery problem

KW - Hypergraph coloring

KW - Orthogonal polygons

UR - http://www.scopus.com/inward/record.url?scp=85040587401&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2018.01.003

DO - 10.1016/j.comgeo.2018.01.003

M3 - Article

AN - SCOPUS:85040587401

VL - 73

SP - 24

EP - 34

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

ER -