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 July 23, 2024 by
Erik Demaine.