Paper by Erik D. Demaine

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(n²) time a sequence of O(n²) moves, each of which rotates just four joints at once.

Comments:

This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1741/17410415.pdf.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 10 pages.

Availability:

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