Abstract
We propose an anytime algorithm to compute successively better approximations of the optimum of Minimum Vertex Guard. Though the presentation is focused on polygons, the work may be directly extended to terrains along the lines of [4]. A major idea in our approach is to explore dominance of visibility regions to first detect pieces that are more difficult to guard.
Work partially supported by funds granted to LIACC through Programa de Financiamento Plurianual, Fundação para a Ciência e Tecnologia and Programa POSI.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Avis, D., Toussaint, G.: An efficient algorithm to decompose a polygon into starshaped pieces. Pattern Recognition 13 (1981) 295–298.
Chvátal, V.: A combinatorial theorem in plane geometry. J. of Combinatorial Theory (Series B) 18 (1975) 39–41.
Edelsbrunner, H., O’Rourke, J., Welzl, E.: Stationing guards in rectilinear art galleries. Computer Vision, Graphics, and Image Processing 27 (1984) 167–176.
Eidenbenz, S.: Approximation algorithms for terrain guarding. Information Processing Letters 82 (2002) 99–105.
Fisk, S.: A short proof of Chvátal’s watchman theorem. J. of Combinatorial Theory (Series B) 24 (1978) 374.
Frühwirth, T., Brisset, P.: Optimal Placement of Base Stations in Wireless Indoor Communication Networks. IEEE Intelligent Systems Magazine 15(1) (2000).
Ghosh, S. K.: Approximation algorithms for art gallery problems. Proc. Canadian Information Processing Society Congress. (1987) 429–434.
Johnson, D.: Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9 (1974) 256–278.
Kahn, J., Klawe, M., Kleitman, D.: Traditional galleries require fewer watchmen. SIAM J. Algebraic and Discrete Methods 4 (1983) 194–206.
Lee, D. T., Lin, A. K.: Computational complexity of art gallery problems. IEEE Transaction on Information Theory IT-32 (1986) 276–282.
Lee, D. T.: Visibility of a simple polygon. Computer Vision, Graphics, and Image Processing 22 (1983) 207–221.
Cormen, T. H., Leiserson, C. E., Rivest, R. L.: Introduction to Algorithms, 11st Ed., MIT Press (1994) 974–978.
Marriott, K., Stuckey, P.: Programming with Constraints — An Introduction, MIT Press (1998).
O’Rourke, J.: An alternate proof of the rectilinear art gallery theorem. J. of Geometry 21 (1983) 118–130.
Sack, J. R., Toussaint, G.: Guard placement in rectilinear polygons. Computational Morphology. G. T. Toussaint, ed., Elsevier Science Publishers (1988) 153–175.
Schuchardt, D., Hecker, H.: Two NP-hard problems for ortho-polygons. Math. Logiv Quart. 41 (1995) 261–267.
Urrutia, J.: Art gallery and illumination problems. In J.-R. Sack and J. Urrutia, editors, Handbook on Computational Geometry. Elsevier (2000).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tomás, A.P., Bajuelos, A.L., Marques, F. (2003). 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) Computational Science — ICCS 2003. ICCS 2003. Lecture Notes in Computer Science, vol 2657. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44860-8_90
Download citation
DOI: https://doi.org/10.1007/3-540-44860-8_90
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40194-0
Online ISBN: 978-3-540-44860-0
eBook Packages: Springer Book Archive