More Web Proxy on the site http://driver.im/

research-article

Algorithm 966: A Practical Iterative Algorithm for the Art Gallery Problem Using Integer Linear Programming

Authors:

Davi C. Tozoni,

Pedro J. De Rezende,

Cid C. De SouzaAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 43, Issue 2

Article No.: 16, Pages 1 - 27

https://doi.org/10.1145/2890491

Published: 16 August 2016 Publication History

Abstract

In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions use Integer Linear Programming (ILP) modeling and rely on state-of-the- art solvers to be able to find optimal solutions for large instances in a matter of minutes. In this work, we discuss an ILP-based algorithm that solves to optimality the Art Gallery Problem (AGP), one of the most studied problems in computational geometry. The basic idea of our method is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. Our algorithm was implemented and tested on almost 3,000 instances and attained optimal solutions for the vast majority of them, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively and efficiently as the one described here. Evidence of its robustness is presented through tests done on a number of classes of polygons of various sizes with and without holes. A software package implementing the algorithm is made available.

Supplementary Material

ZIP File (966.zip)

Software for A Practical Iterative Algorithm for the Art Gallery Problem Using Integer Linear Programming

Download
13.96 MB

References

[1]

Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. 2007. Locating guards for visibility coverage of polygons. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07). SIAM, New Orleans, LA, 1--15.

Digital Library

[2]

John E. Beasley. 1993. Lagrangian relaxation. In Modern Heuristic Techniques for Combinatorial Problems, Colin R. Reeves (Ed.). John Wiley & Sons, New York, NY, 243--303. http://dl.acm.org/ citation.cfm?id==166648.166660

Digital Library

[3]

Dorit Borrmann, Pedro J. de Rezende, Cid C. de Souza, Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller, Andreas Nüchter, Christiane Schmidt, and Davi C. Tozoni. 2013. Point guards and point clouds: Solving general art gallery problems. In Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG'13). ACM, New York, NY, 347--348.

Digital Library

[4]

Prosenjit Bose, Anna Lubiw, and J. Ian Munro. 2002. Efficient visibility queries in simple polygons. Computational Geometry 23, 3 (2002), 313--335.

Digital Library

[5]

Andrea Bottino and Aldo Laurentini. 2011. A nearly optimal algorithm for covering the interior of an art gallery. Pattern Recognition 44, 5 (2011), 1048--1056.

Digital Library

[6]

CGAL. 2012. Computational Geometry Algorithms Library. (2012). www.cgal.org (last accessed January 2012).

[7]

Kyung-Yong Chwa, Byung-Cheol Jo, Christian Knauer, Esther Moet, René van Oostrum, and Chan-Su Shin. 2006. Guarding art galleries by guarding witnesses. International Journal of Computational Geometry And Applications 16, 02n03 (2006), 205--226.

[8]

Marcelo C. Couto, Pedro J. de Rezende, and Cid C. de Souza. 2011. An exact algorithm for minimizing vertex guards on art galleries. International Transactions in Operational Research 18, 4 (2011), 425--448.

[9]

Marcelo C. Couto, Davi C. Tozoni, Pedro J. de Rezende, and Cid C. de Souza. 2013. The Art Gallery Problem Project (point guards). (2013). www.ic.unicamp.br/ &sim; cid/Problem-instances/Art-Gallery.

[10]

Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller, and Christiane Schmidt. 2015. Facets for art gallery problems. Algorithmica 73, 2 (2015), 411--440.

Digital Library

[11]

Subir K. Ghosh. 1987. Approximation algorithms for art gallery problems. In Proceedings of the Canadian Information Processing Society Congress. Canadian Information Processing Society, Mississauga, Ontario, Canada, 429--434.

[12]

Subir K. Ghosh. 2007. Visibility Algorithms in the Plane. Cambridge University Press, New York, NY.

Digital Library

[13]

Subir K. Ghosh. 2010. Approximation algorithms for art gallery problems in polygons. Discrete Applied Mathematics 158, 6 (2010), 718--722.

Digital Library

[14]

GLPK. 2013. GNU Linear Programming Kit. GNU. http://www.gnu.org/software/glpk/ (access December 2013).

[15]

Alexander Kröller, Tobias Baumgartner, Sándor P. Fekete, and Christiane Schmidt. 2012. Exact solutions and bounds for general art gallery problems. Journal on Experimental Algorithmics 17, 1, Article 2.3 (May 2012), 1.13 pages.

Digital Library

[16]

D. T. Lee and Arthur Lin. 1986. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32, 2 (March 1986), 276--282.

Digital Library

[17]

Joseph O'Rourke. 1987. Art Gallery Theorems and Algorithms. Oxford University Press, New York, NY.

Digital Library

[18]

Thomas C. Shermer. 1992. Recent results in art galleries. Proceedings of the IEEE 80, 9 (September 1992), 1384--1399.

[19]

Davi C. Tozoni, Pedro J. de Rezende, and Cid C. de Souza. 2013. The quest for optimal solutions for the art gallery problem: A practical iterative algorithm. In Proceedings of the 12th International Symposium on Experimental Algorithms, (SEA'13) (Lecture Notes in Computer Science), Vincenzo Bonifaci, Camil Demetrescu, and Alberto Marchetti-Spaccamela (Eds.), Vol. 7933. Springer, Rome, Italy, 320--336.

[20]

Jorge Urrutia. 2000. Art gallery and illumination problems. In Handbook of Computational Geometry, J. R. Sack and J. Urrutia (Eds.). Elsevier Science Publishers, Amsterdam, 973--1027.

[21]

Jan van Leeuwen and Anneke A. Schoone. 1981. Untangling a traveling salesman tour in the plane. In Proceedings of the 7th Conference on Graph-Theoretic Concepts in Computer Science. Rijksuniversiteit Vakgroep Informatica, Munich, 87--98. http://books.google.com.br/books?id=LsEuHAAACAAJ.

[22]

XPRESS. 2013. Xpress Optimization Suite. FICO Solutions. http://www.fico.com/en/products/fico-xpress-optim ization-suite (access November 2013).

Cited By

Choe CAhn SDoh NNam C(2023)Reduction of LiDAR Point Cloud Maps for Localization of Resource-Constrained Robotic SystemsIEEE Systems Journal10.1109/JSYST.2022.316292617:1(916-927)Online publication date: Mar-2023
https://doi.org/10.1109/JSYST.2022.3162926
Bertschinger DEl Maalouly NMiltzow TSchnider PWeber S(2023)Topological Art in Simple GalleriesDiscrete & Computational Geometry10.1007/s00454-023-00540-x71:3(1092-1130)Online publication date: 27-Aug-2023
https://doi.org/10.1007/s00454-023-00540-x
Jia FLichti D(2022)A Practical Algorithm for the Viewpoint Planning of Terrestrial Laser ScannersGeomatics10.3390/geomatics20200112:2(181-196)Online publication date: 22-Apr-2022
https://doi.org/10.3390/geomatics2020011
Show More Cited By

Index Terms

Algorithm 966: A Practical Iterative Algorithm for the Art Gallery Problem Using Integer Linear Programming
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming
  2. Mathematical software
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming

Recommendations

A discrete gravitational search algorithm for solving combinatorial optimization problems

Metaheuristics are general search strategies that, at the exploitation stage, intensively exploit areas of the solution space with high quality solutions and, at the exploration stage, move to unexplored areas of the solution space when necessary. The ...
Exact and approximate algorithms for discounted {0-1} knapsack problem

The Discounted {0-1} Knapsack Problem (D{0-1}KP) is an extension of the classical 0-1 knapsack problem (0-1 KP) that consists of selecting a set of item groups where each group includes three items and at most one of the three items can be selected. The ...
Exact Heuristic Algorithm for Traveling Salesman Problem
ICYCS '08: Proceedings of the 2008 The 9th International Conference for Young Computer Scientists

Natural properties of stochastic searching strategies and operations in metaheuristic algorithms have important influence on convergence performance of various metaheuristic algorithms. Through similarity analysis to two kinds of metaheuristic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 43, Issue 2

June 2017

200 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2988256

Editor:
Michael A. Heroux
Sandia National Laboratories, USA

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 August 2016

Accepted: 01 February 2016

Revised: 01 January 2016

Received: 01 January 2015

Published in TOMS Volume 43, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
FAEPEX/UNICAMP
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
353
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Choe CAhn SDoh NNam C(2023)Reduction of LiDAR Point Cloud Maps for Localization of Resource-Constrained Robotic SystemsIEEE Systems Journal10.1109/JSYST.2022.316292617:1(916-927)Online publication date: Mar-2023
https://doi.org/10.1109/JSYST.2022.3162926
Bertschinger DEl Maalouly NMiltzow TSchnider PWeber S(2023)Topological Art in Simple GalleriesDiscrete & Computational Geometry10.1007/s00454-023-00540-x71:3(1092-1130)Online publication date: 27-Aug-2023
https://doi.org/10.1007/s00454-023-00540-x
Jia FLichti D(2022)A Practical Algorithm for the Viewpoint Planning of Terrestrial Laser ScannersGeomatics10.3390/geomatics20200112:2(181-196)Online publication date: 22-Apr-2022
https://doi.org/10.3390/geomatics2020011
Terhar FIcking C(2021)The Sectional Art Gallery and an Evolutionary Algorithm for Approaching Its Minimum Point Guard Problem2021 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC45853.2021.9504843(1390-1397)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1109/CEC45853.2021.9504843
Sapucaia Ade Rezende Pde Souza C(2021)Solving the minimum convex partition of point sets with integer programmingComputational Geometry10.1016/j.comgeo.2021.10179499(101794)Online publication date: Dec-2021
https://doi.org/10.1016/j.comgeo.2021.101794
Kim SLi KCho H(2020)A Flexible Framework for Covering and Partitioning Problems in Indoor SpacesISPRS International Journal of Geo-Information10.3390/ijgi91106189:11(618)Online publication date: 23-Oct-2020
https://doi.org/10.3390/ijgi9110618
Jia FLichti D(2019)A Model-Based Design System for Terrestrial Laser Scanning Networks in Complex SitesRemote Sensing10.3390/rs1115174911:15(1749)Online publication date: 25-Jul-2019
https://doi.org/10.3390/rs11151749
Mitsos ANajman JKevrekidis I(2018)Optimal deterministic algorithm generationJournal of Global Optimization10.1007/s10898-018-0611-871:4(891-913)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s10898-018-0611-8
de Rezende Pde Souza CFriedrichs SHemmer MKröller ATozoni D(2016)Engineering Art GalleriesAlgorithm Engineering10.1007/978-3-319-49487-6_12(379-417)Online publication date: 11-Nov-2016
https://doi.org/10.1007/978-3-319-49487-6_12

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents