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 metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00098832
Contributor : Sylvain Lazard <>
Submitted on : Tuesday, December 15, 2009 - 3:13:48 PM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM
Long-term archiving on : Monday, April 5, 2010 - 11:51:51 PM

File

Convexifying_Monotone_Polygons...
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

184

Files downloads

159