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 http://link.springer.de/link/service/series/0558/papers/1741/17410415.pdf.
- 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
Last updated June 27, 2019 by