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

Engineering Art Galleries

  • Chapter
  • First Online:
Algorithm Engineering

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

Abstract

The Art Gallery Problem (AGP) is one of the most well-known problems in Computational Geometry (CG), with a rich history in the study of algorithms, complexity, and variants. Recently there has been a surge in experimental work on the problem. In this survey, we describe this work, show the chronology of developments, and compare current algorithms, including two unpublished versions, in an exhaustive experiment. Furthermore, we show what core algorithmic ingredients have led to recent successes.

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

Access this chapter

Log in via an institution

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 EPUB and 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

Similar content being viewed by others

Notes

  1. 1.

    This is an an \(O((n+m)\log n)\) sweep line algorithm, where n is the number of polygon vertices and m the number of query points.

  2. 2.

    In the context of fading [43] circular arcs may also be required.

  3. 3.

    Other options are, for instance, leda::rational [46] or CORE::BigRat [39], but, compared to Gmpq, both imply some overhead and are only recommended in case the usage of the more complex number types of these libraries is required.

  4. 4.

    This can be achieved by the instantiation of the Cartesian kernel with \(\texttt {CGAL::Lazy\_exact\_nt{<}CGAL::Gmpq{>}}\).

References

  1. Aigner, M., Ziegler, G.M.: Proofs from THE BOOK, 4th edn. Springer Publishing Company Incorporated, Heidelberg (2009)

    MATH  Google Scholar 

  2. Amit, Y., Mitchell, J.S.B., Packer, E.: Locating guards for visibility coverage of polygons. In: ALENEX, pp. 120–134 (2007)

    Google Scholar 

  3. Amit, Y., Mitchell, J.S.B., Packer, E.: Locating guards for visibility coverage of polygons. Int. J. Comput. Geom. Appl. 20(5), 601–630 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Asano, T.: An efficient algorithm for finding the visibility polygon for a polygonal region with holes. IEICE Trans. 68(9), 557–559 (1985)

    Google Scholar 

  5. Austern, M.H.: Generic Programming and the STL. PUB-AW (1999)

    Google Scholar 

  6. Balas, E., Ng, S.M.: On the set covering polytope: II. lifting the facets with coefficients in \(\{0, 1, 2\}\). Math. Program. 45, 1–20 (1989). doi:10.1007/BF01589093. http://dx.doi.org/10.1007/BF01589093

    Article  MathSciNet  MATH  Google Scholar 

  7. Baumgartner, T., Fekete, S.P., Kröller, A., Schmidt, C.: Exact solutions and bounds for general art gallery problems. In: Proceedings of the SIAM-ACM Workshop on Algorithm Engineering and Experiments, ALENEX 2010, pp. 11–22. SIAM (2010)

    Google Scholar 

  8. Beasley, J.E.: Lagrangian relaxation. In: Reeves, C.R. (ed.) Modern Heuristic Techniques for Combinatorial Problems, pp. 243–303. Wiley, New York (1993). http://dl.acm.org/citation.cfm?id=166648.166660

    Google Scholar 

  9. Bottino, A., Laurentini, A.: A nearly optimal sensor placement algorithm for boundary coverage. Pattern Recogn. 41(11), 3343–3355 (2008)

    Article  MATH  Google Scholar 

  10. Bottino, A., Laurentini, A.: A nearly optimal algorithm for covering the interior of an art gallery. Pattern Recogn. 44(5), 1048–1056 (2011). http://www.sciencedirect.com/science/article/pii/S0031320310005376

    Article  MATH  Google Scholar 

  11. Bungiu, F., Hemmer, M., Hershberger, J., Huang, K., Kröller, A.: Efficient computation of visibility polygons. CoRR abs/1403.3905 (2014). http://arxiv.org/abs/1403.3905

  12. CGAL (Computational Geometry Algorithms Library). http://www.cgal.org/

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

    Article  MathSciNet  MATH  Google Scholar 

  14. Chwa, K., Jo, B., Knauer, C., Moet, E., van Oostrum, R., Shin, C.: Guarding art galleries by guarding witnesses. Int. J. Comput. Geom. Appl. 16(2–3), 205–226 (2006). http://dx.doi.org/10.1142/S0218195906002002

    Article  MathSciNet  MATH  Google Scholar 

  15. Couto, M.C., de Rezende, P.J., de Souza, C.C.: An exact algorithm for an art gallery problem. Technical report IC-09-46, Institute of Computing, University of Campinas, November 2009

    Google Scholar 

  16. Couto, M.C., de Rezende, P.J., de Souza, C.C.: Instances for the art gallery problem (2009). http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery

  17. Couto, M.C., de Rezende, P.J., de Souza, C.C.: An IP solution to the art gallery problem. In: SoCG 2009: Proceedings of the 25th Annual Symposium on Computational Geometry, pp. 88–89. ACM, New York (2009)

    Google Scholar 

  18. Couto, M.C., de Rezende, P.J., de Souza, C.C.: Video: an IP solution to the art gallery problem. In: 18th Video Review of Computational Geometry at the 25th Annual Symposium on Computational Geometry, June 2009. www.computational-geometry.org/SoCG-videos/socg09video/video1-couto.mov

  19. Couto, M.C., de Rezende, P.J., de Souza, C.C.: An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. Oper. Res. 18, 425–448 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Couto, M.C., de Souza, C.C., de Rezende, P.J.: An exact and efficient algorithm for the orthogonal art gallery problem. In: SIBGRAPI 2007: Proceedings of the XX Brazilian Symposium on Computer Graphics and Image Processing, pp. 87–94. IEEE Computer Society, Washington, DC (2007)

    Google Scholar 

  21. Couto, M.C., Souza, C.C., Rezende, P.J.: Experimental evaluation of an exact algorithm for the orthogonal art gallery problem. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 101–113. Springer, Heidelberg (2008). doi:10.1007/978-3-540-68552-4_8

    Chapter  Google Scholar 

  22. IBM ILOG CPLEX Optimization Studio. http://www.ibm.com/software/integration/optimization/cplex-optimizer/

  23. Deshpande, A., Kim, T., Demaine, E.D., Sarma, S.E.: A pseudopolynomial time O(logn)-approximation algorithm for art gallery problems. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 163–174. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73951-7_15

    Chapter  Google Scholar 

  24. Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inf. Process. Lett. 100(6), 238–245 (2006)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  26. Eisenbrand, F., Funke, S., Karrenbauer, A., Matijevic, D.: Energy-aware stage illumination. In: Proceedings of the 21st ACM Symposium on Computational Geometry (SCG 2005), pp. 336–345 (2005). http://portal.acm.org/citation.cfm?doid=1064092.1064144

  27. Erdem, U.M., Sclaroff, S.: Optimal placement of cameras in floorplans to satisfy task requirements and cost constraints. In: Proceedings of the Fifth International Workshop on Omnidirectional Vision, Camera Networks and Non-classical Cameras, pp. 30–41 (2004)

    Google Scholar 

  28. Erdem, U.M., Sclaroff, S.: Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements. Comput. Vis. Image Underst. 103(3), 156–169 (2006)

    Article  Google Scholar 

  29. Ernestus, M., Friedrichs, S., Hemmer, M., Kokemüller, J., Kröller, A., Moeini, M., Schmidt, C.: Algorithms for art gallery illumination. arXiv e-prints, October 2014

    Google Scholar 

  30. Fekete, S.P., Friedrichs, S., Kröller, A., Schmidt, C.: Facets for art gallery problems. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 208–220. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38768-5_20

    Chapter  Google Scholar 

  31. Fekete, S.P., Friedrichs, S., Kröller, A., Schmidt, C.: Facets for art gallery problems. Algorithmica 73(2), 411–440 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  32. Fisk, S.: A short proof of Chvátal’s watchman theorem. J. Comb. Theory Ser. B 24(3), 374–375 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  33. Friedrichs, S.: Integer solutions for the art gallery problem using linear programming. Master’s thesis, TU Braunschweig (2012)

    Google Scholar 

  34. Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons and terrains. In: Rahman, M.S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 21–34. Springer, Heidelberg (2010). doi:10.1007/978-3-642-11440-3_3

    Chapter  Google Scholar 

  35. GNU Multiple Precision Arithmetic Library (2013). http://gmplib.org

  36. Hemmer, M., Huang, K., Bungiu, F.: 2D visibility. In: CGAL User and Reference Manual. CGAL Editorial Board (2014, to appear)

    Google Scholar 

  37. Honsberger, R.: Mathematical Gems II. Mathematical Association of America, Washington, DC (1976)

    MATH  Google Scholar 

  38. Kahn, J., Klawe, M., Kleitman, D.: Traditional art galleries require fewer watchmen. SIAM J. Algebr. Discrete Methods 4(2), 194–206 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  39. Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.: A core library for robust numeric and geometric computation. In: Proceedings of the 15th Annual ACM Symposium of Computational Geometry (SCG), pp. 351–359 (1999)

    Google Scholar 

  40. Kokemüller, J.: Variants of the art gallery problem. Master’s thesis, TU Braunschweig (2014)

    Google Scholar 

  41. Kröller, A., Baumgartner, T., Fekete, S.P., Schmidt, C.: Exact solutions and bounds for general art gallery problems. ACM J. Exp. Algothmmics 17, Article ID 2.3 (2012)

    Google Scholar 

  42. Kröller, A., Moeini, M., Schmidt, C.: A novel efficient approach for solving the art gallery problem. In: Ghosh, S.K., Tokuyama, T. (eds.) WALCOM 2013. LNCS, vol. 7748, pp. 5–16. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36065-7_3

    Chapter  Google Scholar 

  43. Kröller, A., Schmidt, C.: Energy-aware art gallery illumination. In: Proceedings of the 28th European Workshop on Computational Geometry (EuroCG 2012), pp. 93–96 (2012)

    Google Scholar 

  44. Laurentini, A.: Guarding the walls of an art gallery. Vis. Comput. 15(6), 265–278 (1999)

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  46. Mehlhorn, K., Näher, S.: Leda: A Platform for Combinatorial and Geometric Computing. PUB-CAMB, Cambridge (2000)

    MATH  Google Scholar 

  47. Mitchell, J.S.B.: Approximating watchman routes. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, NewOrleans, Louisiana, USA, 6-8 January 2013, pp. 844–855 (2013)

    Google Scholar 

  48. Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1362–1373. Springer, Heidelberg (2005). doi:10.1007/11523468_110

    Chapter  Google Scholar 

  49. O’Rourke, J.: Art Gallery Theorems and Algorithms. International Series of Monographs on Computer Science. Oxford University Press, New York (1987)

    MATH  Google Scholar 

  50. O’Rourke, J., Supowit, K.: Some NP-hard polygon decomposition problems. IEEE Trans. Inf. Theory 29(2), 181–190 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  51. Packer, E.: Computing multiple watchman routes. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 114–128. Springer, Heidelberg (2008). doi:10.1007/978-3-540-68552-4_9

    Chapter  Google Scholar 

  52. Packer, E.: Robust geometric computing and optimal visibility coverage. Ph.D. thesis, SUNY Stony Brook (2008)

    Google Scholar 

  53. Tao, P.D., An, L.T.H.: Convex analysis approach to D.C. programming: theory, algorithms and applications. Acta Mathematica Vietnamica 22(1), 289–355 (1997)

    MathSciNet  MATH  Google Scholar 

  54. Pion, S., Fabri, A.: A generic lazy evaluation scheme for exact geometric computations. In: 2nd # WOR-LCSD (2006). http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0608063

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  57. Tomás, A.P., Bajuelos, A.L., Marques, F.: Approximation algorithms to minimum vertex cover problems on polygons and terrains. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Dongarra, J.J., Zomaya, A.Y., Gorbachev, Y.E. (eds.) ICCS 2003. LNCS, vol. 2657, pp. 869–878. Springer, Heidelberg (2003). doi:10.1007/3-540-44860-8_90

    Chapter  Google Scholar 

  58. Tomás, A.P., Bajuelos, A.L., Marques, F.: On visibility problems in the plane - solving minimum vertex guard problems by successive approximations. In: Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics (AI & MATH 2006) (2006, to appear)

    Google Scholar 

  59. Tozoni, D.C., de Rezende, P.J., de Souza, C.C.: Algorithm 966: a practical iterative algorithm for the art gallery problem using integer linear programming. ACM Trans. Math. Softw. 43(2), 16:1–16:27 (2016). doi:10.1145/2890491. Article no. 16

    Article  Google Scholar 

  60. Tozoni, D.C., Rezende, P.J., 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). doi:10.1007/978-3-642-38527-8_29

    Chapter  Google Scholar 

  61. Urrutia, J.: Art gallery and illumination problems. In: Sack, J.R., Urrutia, J. (eds.) Handbook on Computational Geometry, pp. 973–1026. Elsevier Science Publishers, Amsterdam (2000)

    Chapter  Google Scholar 

  62. Wein, R., Berberich, E., Fogel, E., Halperin, D., Hemmer, M., Salzman, O., Zukerman, B.: 2D arrangements. In: CGAL User and Reference Manual, 4.0 edn., CGAL Editorial Board (2012)

    Google Scholar 

Download references

Acknowledgments

Many people have contributed to the developments described in this paper. In particular, the authors would like to thank Tobias Baumgartner, Marcelo C. Couto, Sándor P. Fekete, Winfried Hellmann, Mahdi Moeini, Eli Packer, and Christiane Schmidt.

Stephan Friedrichs was affiliated with TU Braunschweig, IBR during most of the research.

This work was partially supported by the Deutsche Forschungsgemeinschaft (DFG) under contract number KR 3133/1-1 (Kunst!), by Fundação de Amparo à Pesquisa do Estado de São Paulo (Fapesp, #2007/52015-0, #2012/18384-7), Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, grants #311140/2014-9, #477692/2012-5 and #302804/2010-2), and Faepex/Unicamp. Google Inc. supported the development of the Computational Geometry Algorithms Library [12] (CGAL) visibility package through the 2013 Google Summer of Code.

Author information

Authors and Affiliations

  1. Institute of Computing, University of Campinas, Campinas, Brazil

    Pedro J. de Rezende, Cid C. de Souza & Davi C. Tozoni

  2. Max Planck Institute for Informatics, Saarbrücken, Germany

    Stephan Friedrichs

  3. TU Braunschweig, IBR, Algorithms Group, Braunschweig, Germany

    Michael Hemmer & Alexander Kröller

Authors
  1. Pedro J. de Rezende
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cid C. de Souza
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stephan Friedrichs
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michael Hemmer
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Alexander Kröller
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Davi C. Tozoni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pedro J. de Rezende .

Editor information

Editors and Affiliations

  1. Kiel University , Kiel, Germany

    Lasse Kliemann

  2. Karlsruhe Institute of Technology , Karlsruhe, Germany

    Peter Sanders

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing AG

About this chapter

Cite this chapter

de Rezende, P.J., de Souza, C.C., Friedrichs, S., Hemmer, M., Kröller, A., Tozoni, D.C. (2016). Engineering Art Galleries. In: Kliemann, L., Sanders, P. (eds) Algorithm Engineering. Lecture Notes in Computer Science(), vol 9220. Springer, Cham. https://doi.org/10.1007/978-3-319-49487-6_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-49487-6_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-49486-9

  • Online ISBN: 978-3-319-49487-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation