Top

Published in:

2020 | OriginalPaper | Chapter

Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons

Authors : Chuzo Iwamoto, Tatsuaki Ibusuki

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is \(k=2\). Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is \(k=2\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Reconfiguring k-path Vertex Covers

next chapter Maximum Bipartite Subgraph of Geometric Intersection Graphs

Bärtschi, A., Suri, S.: Conflict-free chromatic art gallery coverage. In: 29th International Symposium on Theoretical Aspects of Computer Science, pp. 160–171 (2012)

Çağırıcı, O., Ghosh, S.K., Hliněný, P., Roy, R.: On conflict-free chromatic guarding of simple polygons. arXiv:1904.08624, 26 pages (2019)

Chvátal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory B 18, 39–41 (1975)MathSciNetCrossRef

Eidenbenz, S.J., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31, 79–113 (2001)MathSciNetCrossRef

Erickson, L.H., LaValle, S.M.: A chromatic art gallery problem. Technical report, Department of Computer Science, University of Illinois at Urbana-Champaign (2011)

Fekete, S.P., Friedrichs, S., Hemmer, M., Mitchell, J.B.M., Schmidt, C.: On the chromatic art gallery problem. In: 30th Canadian Conference on Computational Geometry, Halifax, pp. 73–79 (2014)

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)MATH

Hoffmann, F.: On the rectilinear art gallery problem. In: Paterson, M.S. (ed.) ICALP 1990. LNCS, vol. 443, pp. 717–728. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0032069CrossRef

Hoffman, F., Kriegel, K., Suri, S., Verbeek, K., Willert, M.: Tight bounds for conflict-free chromatic guarding of orthogonal art galleries. Comput. Geom. Theory Appl. 73, 24–34 (2018)MathSciNetCrossRef

10.

Iwamoto, C., Kume, T.: Computational complexity of the \(r\)-visibility guard set problem for polyominoes. In: Akiyama, J., Ito, H., Sakai, T. (eds.) JCDCGG 2013. LNCS, vol. 8845, pp. 87–95. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13287-7_8CrossRefMATH

11.

Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comput. Geom. Theory Appl. 39(3), 219–228 (2008)MathSciNetCrossRef

12.

Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276–282 (1986)MathSciNetCrossRef

13.

O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, New York (1987)MATH

14.

Pilz, A: Planar 3-SAT with a clause-variable cycle. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory, pp. 31:1–31:13 (2018)

15.

Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. MCS. Springer, New York (1985). https://doi.org/10.1007/978-1-4612-1098-6CrossRefMATH

16.

Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Q. 41(2), 261–267 (1995)MathSciNetCrossRef

17.

Worman, C., Keil, J.M.: Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geom. Appl. 17(2), 105–138 (2007)MathSciNetCrossRef

Title: Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons
Authors: Chuzo Iwamoto
Tatsuaki Ibusuki
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner