Skip to Main content Skip to Navigation
Conference papers

Convexifying Monotone Polygons

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Sylvain Lazard <>
Submitted on : Tuesday, December 15, 2009 - 3:13:48 PM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM
Long-term archiving on: : Monday, April 5, 2010 - 11:51:51 PM


Files produced by the author(s)




Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss. Convexifying Monotone Polygons. 10th Annual International Symposium on Algorithms & Computation - ISAAC'99, Kamakoti V (IMSC, India) Rangarajan K (MCC, India) Rama R (IIT, Madras, India) Boopal E (IIT, Madras, India), Dec 1999, Chennai, India. 10 p, ⟨10.1007/3-540-46632-0_42⟩. ⟨inria-00098832⟩



Record views


Files downloads