Paper by Erik D. Demaine

Reference:
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, and Michael A. Soss, “Convexifying Monotone Polygons”, Technical Report CS-99-03, Department of Computer Science, University of Waterloo, March 1999.

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.

Length:
The paper is 12 pages.

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

Related papers:
ISAAC99 (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 March 27, 2017 by Erik Demaine.