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.

BibTeX

@TechReport{MonotonePolygonsTR,
  AUTHOR        = {Therese C. Biedl and Erik D. Demaine and Sylvain Lazard and
                   Steven M. Robbins and Michael A. Soss},
  TITLE         = {Convexifying Monotone Polygons},
  INSTITUTION   = {Department of Computer Science, University of Waterloo},
  INSTITUTIONURL = {http://www.cs.uwaterloo.ca/},
  NUMBER        = {CS-99-03},
  NUMBERURL     = {http://www.cs.uwaterloo.ca/cs-archive/CS-1999/CS-1999.shtml#03},
  MONTH         = {March},
  YEAR          = 1999,

  LENGTH        = {12 pages},
  PAPERS        = {ISAAC99},
  WEBPAGES      = {linkage},
}

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.

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