HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, December 15, 2009 - 3:13:48 PM
Last modification on : Friday, February 4, 2022 - 3:19:37 AM
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