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

https://hal.inria.fr/inria-00098832
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

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

212

Files downloads

298