Abstract
Recently introduced in [1], the Chromatic Art Gallery Problem (CAGP) is related to the well known Art Gallery Problem to the extent that given a polygon P, a set of guards within P that satisfies a particular property is sought. Define a proper coloring of a guard set that covers the polygon as a color assignment in which any two guards receive different colors whenever their visibility regions intersect. The CAGP aims to find among the sets of guards that cover P one that admits a proper coloring of smallest cardinality. In this paper, we present an Integer Programming formulation for a discrete version of the CAGP and introduce techniques that allow us to attain proven optimal solutions for a variety of instances of the problem. Experiments were conducted considering vertex guards, but the method clearly works for any discrete set of guard candidates that guarantee full polygon coverage. Having been absent from the literature so far, experimental results are also discussed showing that this approach is of practical value.
This research was supported by grants from Capes #P-26329-2012, CNPq #477692/2012-5, #302804/2010-2, and Fapesp #2007/52015-0, #2012/24993-6.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Erickson, L.H., LaValle, S.M.: An art gallery approach to ensuring that landmarks are distinguishable. In: Durrant-Whyte, H.F., Roy, N., Abbeel, P. (eds.) Robotics: Science and Systems (2011)
ORourke, J.: Art Gallery Theorems and Algorithms. Oxford Univ. Press, USA (1987)
Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Proc. of the Canadian Information Processing Society Congress, pp. 429–434 (1987)
Shermer, T.: Recent results in art galleries. Proc. of IEEE 80(9), 1384–1399 (1992)
Urrutia, J.: Art gallery and illumination problems. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 973–1027. North-Holland (2000)
Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge U. Press, USA (2007)
Erickson, L.H., LaValle, S.M.: How many landmark colors are needed to avoid confusion in a polygon? In: Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 2302–2307. IEEE (2011)
Lee, D.T., Lin, A.: Computational complexity of art gallery problems. IEEE Transactions on Information Theory 32(2), 276–282 (1986)
Schuchardt, D., Hecker, H.D.: Two NP-hard art-gallery problems for ortho-polygons. Mathematical Logic Quarterly 41, 261–267 (1995)
Brodn, B., Hammar, M., Nilsson, B.J.: Guarding lines and 2-link polygons is APX-hard. In: Proc. of the 13th Canad. Conf. on Comput. Geom., pp. 45–48 (2001)
Fekete, S.P., Friedrichs, S., Friedrichs, S.: Complexity of the general chromatic art gallery problem. In: Proc. of 30th European Workshop on Comput. Geom. (2014)
Erickson, L.H., LaValle, S.M.: Navigation among visually connected sets of partially distinguishable landmarks. In: Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 4829–4835. IEEE (2012)
Bärtschi, A., Suri, S.: Conflict-free chromatic art gallery coverage. Algorithmica, 1–19 (2013)
Amit, Y., Mitchell, J.S.B., Packer, E.: Locating guards for visibility coverage of polygons. Int. J. of Comput. Geom. & Appl. 20(5), 601–630 (2010)
Bottino, A., Laurentini, A.: A nearly optimal algorithm for covering the interior of an art gallery. Pattern Recognition 44(5), 1048–1056 (2011)
Kröller, A., Baumgartner, T., Fekete, S.P., Schmidt, C.: Exact solutions and bounds for general art gallery problems. J. of Exper. Algorit. 17(1), 2.1–2.23 (2012)
Tozoni, D.C., de Rezende, P.J., de Souza, C.C.: The quest for optimal solutions for the art gallery problem: A practical iterative algorithm. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 320–336. Springer, Heidelberg (2013)
Borrmann, D., de Rezende, P.J., de Souza, C.C., Fekete, S.P., Friedrichs, S., Kröller, A., Nüchter, A., Schmidt, C., Tozoni, D.C.: Point guards and point clouds: solving general art gallery problems. In: Proc. of the 29th Annual Symposium on Computational Geometry, SoCG 2013, pp. 347–348. ACM, USA (2013)
Couto, M.C., de Rezende, P.J., de Souza, C.C.: An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. in Operat. Res. 18(4), 425–448 (2011)
Crepaldi, B., de Rezende, P.J., de Souza, C.C.: An efficient exact algorithm for the natural wireless localization problem. In: Proc. of the 25th Canad. Conf. on Comput. Geom. (2013)
Chwa, K., Jo, B., Knauer, C., Moet, E., van Oostrum, R., Shin, C.: Guarding art galleries by guarding witnesses. Int. J. of Comp. Geom. & Appl. 16, 205–226 (2006)
Bose, P., Lubiw, A., Munro, J.I.: Efficient visibility queries in simple polygons. Comput. Geom. Theory Appl. 23(3), 313–335 (2002)
Couto, M.C., de Rezende, P.J., de Souza, C.C.: Instances for the Art Gallery Problem (2009), www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/AGPVG
Tozoni, D.C., de Rezende, P.J., de Souza, C.C.: The Art Gallery Problem Project (2013), http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/AGPPG
Crepaldi, B.E., de Rezende, P.J., de Souza, C.C.: Instances for the Natural Wireless Localization Problem (2013), http://www.ic.unicamp.br/~cid/Problem-instances/Wireless-Localization
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Zambon, M.J.O., de Rezende, P.J., de Souza, C.C. (2014). An Exact Algorithm for the Discrete Chromatic Art Gallery Problem. In: Gudmundsson, J., Katajainen, J. (eds) Experimental Algorithms. SEA 2014. Lecture Notes in Computer Science, vol 8504. Springer, Cham. https://doi.org/10.1007/978-3-319-07959-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-07959-2_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07958-5
Online ISBN: 978-3-319-07959-2
eBook Packages: Computer ScienceComputer Science (R0)