Abstract
One strategy for the enumeration of a class of objects is local transformation, in which new objects of the class are produced by means of a small modification of a previously-visited object in the same class. When local transformation is possible, the operation can be used to generate objects of the class via random walks, and as the basis for such optimization heuristics as simulated annealing.
For general simple polygons on fixed point sets, it is still not known whether the class of polygons on the set is connected via a constant-size local transformation. In this paper, we exhibit a simple local transformation for which the classes of (weakly) edge-visible and (weakly) externally visible polygons are connected. The latter class is particularly interesting as it is the most general polygon class known to be connected under local transformation.
Partially supported by CUR Gen. Cat. 1999SGR00356 and MEC-DGES-SEUID PB98-0933
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
D. Avis and K. Fukuda, ‘Reverse search for enumeration,’ Discr. Appl. Math. 65:21–46, 1996.
D. Avis and G. T. Toussaint, ‘An optimal algorithm for determining the visibility of a polygon from an edge,’ IEEE Trans. Comput. C-30:910–914, 1981.
H. Edelsbrunner and N. R. Shah, ‘Incremental topological flipping works for regular triangulations,’ Algorithmica 15:223–241, 1996.
S. Fortune, ‘Voronoi diagrams and Delaunay triangulations,’ in Computing in Euclidean Geometry, D. Z. Du and F. K. Hwang, eds., World Scientific, pp. 193–234, 1992.
C. Hernando, F. Hurtado, A. Márquez, M. Mora and M. Noy, ‘Geometric tree graphs of points in convex position,’ Discr. Appl. Math. 93:51–66, 1999.
C. Hernando, F. Hurtado and M. Noy, ‘Graphs of non-crossing matchings,’ Proc. 15th European Conference on Computational Geometry, pp. 97–100, 1999.
J. Hershberger, ‘Finding the visibility graph of a simple polygon in time proportional to its size,’ Algorithmica 4:141–155, 1989.
M. E. Houle, ‘On local transformations of simple polygons,’ Australian Comp. Sci. Commun. 18(3):64–71 (Proc. CATS’96, Melbourne), 1996.
F. Hurtado and M. Noy, ‘Graphs of triangulations of a convex polygon and tree of triangulations,’ Comput. Geom. Theory Appl. 13:179–188, 1999.
F. Hurtado, M. Noy and J. Urrutia, ‘Flipping edges in triangulations,’ Discr. Comp. Geom. 22:333–346, 1999.
B. Joe, ‘Construction of three-dimensional Delaunay triangulations using local transformations’, Computer Aided Geom. Design 8:123–142, 1991.
C. L. Lawson, ‘Transforming triangulations,’ Discr. Math. 3:365–372, 1972.
J. O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.
M. Pocchiola and G. Vegter, ‘Computing the visibility graph via pseudotriangulations’ Proc. 11th ACM Symp. Comp. Geom., 1995, pp. 248–257.
C. Zhu, G. Sundaram, J. Snoeyink, and J. S. B. Mitchell, ‘Generating random polygons with given vertices,’ Comput. Geom. Theory Appl. 6:277–290, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hernando, C., Houle, M.E., Hurtado, F. (2000). On Local Transformation of Polygons with Visibility Properties. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_6
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive