Paper by Erik D. Demaine

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.

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.

This paper is also available from the electronic LNCS volume as

The paper is \copyright Springer-Verlag.

The paper is 10 pages.

The paper is available in PostScript (198k).
See information on file formats.
[Google Scholar search]

Related papers:
MonotonePolygonsTR (Convexifying Monotone Polygons)

Related webpages:
Carpenter's Rule Theorem

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.