Convexifying Monotone Polygons

Therese C. Biedl; Erik D. Demaine; Sylvain Lazard; Steven M. Robbins; Michael A. Soss

Convexifying Monotone Polygons

Therese C. Biedl ¹ Erik D. Demaine ¹ Sylvain Lazard ² Steven M. Robbins ³ Michael A. Soss ³

1 CPSC - Department of Computer Science [Calgary]

2 ISA - Models, algorithms and geometry for computer graphics and vision

INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

3 SCS - School of computer science [Ottawa]

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.

Mots-clés : linkages mécanismes articulés

Document type :

Conference papers

Domain :

Computer Science [cs] / Other [cs.OH]

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

Convexifying_Monotone_Polygons...

Files produced by the author(s)

Convexifying Monotone Polygons

File

Identifiers

Collections

Citation

Export

Metrics

184

159

Contact

Convexifying Monotone Polygons

File

Identifiers

Collections

Citation

Export

Share

Metrics

184

159

Contact