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.

BibTeX

@InProceedings{ISAAC99,
  AUTHOR        = {Therese C. Biedl and Erik D. Demaine and Sylvain Lazard and
                   Steven M. Robbins and Michael A. Soss},
  TITLE         = {Convexifying Monotone Polygons},
  BOOKTITLE     = {Proceedings of the 10th Annual International Symposium on
                   Algorithms and Computation (ISAAC'99)},
  BOOKURL       = {http://www.nishizeki.ecei.tohoku.ac.jp/nszk/nishi/isaac/isaac99/content99.html},
  ADDRESS       = {Chennai, India},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 1741,
  MONTH         = {December 16--18},
  YEAR          = 1999,
  PAGES         = {415--424},

  LENGTH        = {10 pages},
  PAPERS        = {MonotonePolygonsTR},
  COPYRIGHT     = {The paper is \copyright Springer-Verlag.},
  doi           = {https://dx.doi.org/10.1007/3-540-46632-0_42},
  dblp          = {https://dblp.org/rec/conf/isaac/BiedlDLRS99},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/3-540-46632-0_42">SpringerLink</A>.},
  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.

Comments:

This paper is also available from SpringerLink.

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