[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

An Exact Algorithm for the Discrete Chromatic Art Gallery Problem

  • Conference paper
Experimental Algorithms (SEA 2014)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8504))

Included in the following conference series:

  • 1771 Accesses

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Google Scholar 

  2. ORourke, J.: Art Gallery Theorems and Algorithms. Oxford Univ. Press, USA (1987)

    Google Scholar 

  3. Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Proc. of the Canadian Information Processing Society Congress, pp. 429–434 (1987)

    Google Scholar 

  4. Shermer, T.: Recent results in art galleries. Proc. of IEEE 80(9), 1384–1399 (1992)

    Article  Google Scholar 

  5. Urrutia, J.: Art gallery and illumination problems. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 973–1027. North-Holland (2000)

    Google Scholar 

  6. Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge U. Press, USA (2007)

    Book  MATH  Google Scholar 

  7. 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)

    Google Scholar 

  8. Lee, D.T., Lin, A.: Computational complexity of art gallery problems. IEEE Transactions on Information Theory 32(2), 276–282 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  9. Schuchardt, D., Hecker, H.D.: Two NP-hard art-gallery problems for ortho-polygons. Mathematical Logic Quarterly 41, 261–267 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  10. 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)

    Google Scholar 

  11. 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)

    Google Scholar 

  12. 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)

    Google Scholar 

  13. Bärtschi, A., Suri, S.: Conflict-free chromatic art gallery coverage. Algorithmica, 1–19 (2013)

    Google Scholar 

  14. 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)

    Article  MATH  MathSciNet  Google Scholar 

  15. Bottino, A., Laurentini, A.: A nearly optimal algorithm for covering the interior of an art gallery. Pattern Recognition 44(5), 1048–1056 (2011)

    Article  MATH  Google Scholar 

  16. 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)

    Google Scholar 

  17. 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)

    Chapter  Google Scholar 

  18. 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)

    Chapter  Google Scholar 

  19. 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)

    Article  MATH  Google Scholar 

  20. 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)

    Google Scholar 

  21. 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)

    Article  MATH  Google Scholar 

  22. Bose, P., Lubiw, A., Munro, J.I.: Efficient visibility queries in simple polygons. Comput. Geom. Theory Appl. 23(3), 313–335 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  23. 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

  24. 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

  25. 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

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics