LIPIcs.SoCG.2020.80.pdf
- Filesize: 0.58 MB
- 5 pages
Document
Designing Art Galleries (Media Exposition)
Authors
Kevin Buchin 
,
Irina Kostitsyna ,
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Cite AsGet BibTex
Toon van Benthem, Kevin Buchin, Irina Kostitsyna, and Stijn Slot. Designing Art Galleries (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 80:1-80:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.80
https://doi.org/10.4230/LIPIcs.SoCG.2020.80
Abstract
We present a method for generating interesting levels based on several NP-hardness reductions for a puzzle game based on the Art Gallery problem.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Art Gallery problem
- NP-hard
- puzzle
- level generation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Yoav Amit, Joseph S.B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. International Journal of Computational Geometry & Applications, 20(05):601-630, 2010.
-
Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke. Ruler of the plane - games of geometry (multimedia contribution). In Proc. 33rd International Symposium on Computational Geometry (SoCG), pages 63:1-63:5, 2017.
-
Der-Tsai Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32(2):276-282, 1986.
-
David Lichtenstein. Planar formulae and their uses. SIAM Journal on Computing, 11(2):329-343, 1982.