Experimental Evaluation Of An Exact Algorithm For The Orthogonal Art Gallery Problem

dc.creatorCouto M.C.
dc.creatorDe Souza C.C.
dc.creatorDe Rezende P.J.
dc.date2008
dc.date2015-06-30T19:30:27Z
dc.date2015-11-26T14:45:01Z
dc.date2015-06-30T19:30:27Z
dc.date2015-11-26T14:45:01Z
dc.date.accessioned2018-03-28T21:54:06Z
dc.date.available2018-03-28T21:54:06Z
dc.identifier3540685480; 9783540685487
dc.identifierLecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 5038 LNCS, n. , p. 101 - 113, 2008.
dc.identifier3029743
dc.identifier10.1007/978-3-540-68552-4_8
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-45449109184&partnerID=40&md5=b10c882f5ddf1aafcafd7f4ff273937a
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/106523
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/106523
dc.identifier2-s2.0-45449109184
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1252342
dc.descriptionWe consider the Orthogonal Art Gallery problem (oagp) whose goal is to minimize the number of vertex guards required to watch an art gallery whose boundary is an n-vertex orthogonal polygon P. Here, we explore an exact algorithm for oagp, which we proposed in [1], that iteratively computes optimal solutions to Set Cover problems (scps) corresponding to discretizations of P. While it is known [1] that this procedure converges to an exact solution of the original continuous problem, the number of iterations executed is highly dependent on the way we discretize P. Although the best theoretical bound for convergence is Θ(n 3) iterations, we show that, in practice, it is achieved after only a few of them, even for random polygons of hundreds of vertices. As each iteration involves the solution of an scp, the strategy for discretizing P is of paramount importance. In this paper, we carry out an extensive empirical investigation with five alternative discretization strategies to implement the algorithm. A broad range of polygon classes is tested. As a result, we are able to significantly improve the performance of the algorithm, while maintaining low execution times, to the point that we achieve a fivefold increase in polygon size, compared to the literature. © 2008 Springer-Verlag Berlin Heidelberg.
dc.description5038 LNCS
dc.description
dc.description101
dc.description113
dc.descriptionCouto, M.C., de Souza, C.C., de Rezende, P.J., An exact and efficient algorithm for the orthogonal art gallery problem (2007) Proc. of the XX Brazilian Symp. on Comp. Graphics and Image Processing, pp. 87-94. , IEEE Computer Society, Los Alamitos
dc.descriptionHonsberger, R., Mathematical Gems II (1976) Dolciani Mathematical Expositions, (2). , in The, Mathematical Association of America
dc.descriptionChvátal, V., A combinatorial theorem in plane geometry (1975) Journal of Combinatorial Theory Series B, 18, pp. 39-41
dc.descriptionUrrutia, J., Art gallery and illumination problems (2000) Handbook of Computational Geometry, pp. 973-1027. , Sack, J.R, Urrutia, J, eds, North-Holland, Amsterdam
dc.descriptionKahn, J., Klawe, M.M., Kleitman, D., Traditional galleries require fewer watchmen (1983) SIAM J. Algebraic Discrete Methods, 4, pp. 194-206
dc.descriptionSchuchardt, D., Hecker, H.D., Two NP-hard art-gallery problems for ortho-polygons (1995) Mathematical Logic Quarterly, 41, pp. 261-267
dc.descriptionSack, J.R., Toussaint, G.T., Guard placement in rectilinear polygons (1988) Computational Morphology, pp. 153-175. , Toussaint, G.T, ed, North-Holland, Amsterdam
dc.descriptionEdelsbrunner, H., O'Rourke, J., Welzl, E., Stationing guards in rectilinear art galleries (1984) Comput. Vision Graph. Image Process, 27, pp. 167-176
dc.descriptionGhosh, S.K., Approximation algorithms for art gallery problems (1987) Proc. Canadian Inform. Process, , Soc. Congress
dc.descriptionEidenbenz, S., Approximation algorithms for terrain guarding (2002) Inf. Process. Lett, 82 (2), pp. 99-105
dc.descriptionAmit, Y., Mitchell, J.S.B., Packer, E., Locating guards for visibility coverage of polygons (2007) Proc. Workshop on Algorithm Eng. and Experiments, pp. 1-15
dc.descriptionErdem, U.M., Sclaroff, S., Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements (2006) Comput. Vis. Image Underst, 103 (3), pp. 156-169
dc.descriptionTomás, A.P., Bajuelos, A.L., Marques, F., On visibility problems in the plane -solving minimum vertex guard problems by successive approximations (2006) Proc. of the 9th Int. Symp. on Artificial Intelligence and Mathematics
dc.descriptionCouto, M.C., de Souza, C.C., de Rezende, P.J., OAGPLIB - Orthogonal art gallery problem library, , www.ic.unicamp.br/∼cid/Problem-instances/Art-Gallery
dc.descriptionJohnson, D.S.: A theoretician's guide to the experimental analysis of algorithms. In: M.H.G., et al. (eds.) Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implem. Challenges, AMS, Providence, pp. 215-250 (2002)McGeoch, C.C., Moret, B.M.E., How to present a paper on experimental work with algorithms (1999) SIGACT News, p. 30
dc.descriptionSanders, P., (2002) Presenting data from experiments in algorithmics, pp. 181-196. , Springer, New York
dc.descriptionMoret, B., Towards a discipline of experimental algorithmics Proc. 5th DIMACS Challenge
dc.descriptionLee, D.T., Visibility of a simple polygon. Comput (1983) Vision, Graphics, and Image Process, 22, pp. 207-221
dc.descriptionJoe, B., Simpson, R.B., Visibility of a simple polygon from a point (1985), Report CS-85-38, Dept. Math. Comput. Sci, Drexel Univ, Philadelphia, PAJoe, B., Simpson, R.B., Correction to Lee's visibility polygon algorithm (1987) BIT, 27, pp. 458-473
dc.descriptionBose, P., Lubiw, A., Munro, J.I., Efficient visibility queries in simple polygons (2002) Computational Geometry, 23 (3), pp. 313-335
dc.descriptionTomás, A.P., Bajuelos, A.L., Generating random orthogonal polygons (2004) LNCS (LNAI, 3040, pp. 364-373. , Conejo, R, Urretavizcaya, M, Pérez-de-la-Cruz, J.-L, eds, CAEPIA/TTIA 2003, Springer, Heidelberg
dc.descriptionFalconer, K., (1990) Fractal Geometry, Mathematical Foundations and Applications, pp. 120-121. , John Wiley & Sons, Chichester
dc.languageen
dc.publisher
dc.relationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsfechado
dc.sourceScopus
dc.titleExperimental Evaluation Of An Exact Algorithm For The Orthogonal Art Gallery Problem
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución