Convexifying Monotone Polygons

Reference:
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, and Michael A. Soss, ``Convexifying Monotone Polygons,'' in Proceedings of the 10th Annual International Symposium on Algorithms and Computation (ISAAC'99), Lecture Notes in Computer Science, volume 1741, Chennai, India, December 16-18, 1999, pages 415-424.

Abstract:
This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a convex polygon; a polygon is monotone if any vertical line intersects the interior at a (possibly empty) interval. Our algorithm computes in O(n2) time a sequence of O(n2) moves, each of which rotates just four joints at once.

Copyright:
© Springer-Verlag.

Length:
10 pages.

Availability:
Compressed postscript file: ISAAC'99 (72k).



Return to previous page


Sylvain Lazard
Last modified: Wed Feb 16 09:41:53 MET 2000