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.
Type de document :
Communication dans un congrès
Alok Aggarwal and C. Pandu Rangan. 10th Annual International Symposium on Algorithms & Computation - ISAAC'99, Dec 1999, Chennai, India. Springer-Verlag, LNCS 1741, 10 p, 1999, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/550xbyrwva7rew49/fulltext.pdf〉. 〈10.1007/3-540-46632-0_42〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00098832
Contributeur : Sylvain Lazard <>
Soumis le : mardi 15 décembre 2009 - 15:13:48
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:51:51

Fichier

Convexifying_Monotone_Polygons...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss. Convexifying Monotone Polygons. Alok Aggarwal and C. Pandu Rangan. 10th Annual International Symposium on Algorithms & Computation - ISAAC'99, Dec 1999, Chennai, India. Springer-Verlag, LNCS 1741, 10 p, 1999, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/550xbyrwva7rew49/fulltext.pdf〉. 〈10.1007/3-540-46632-0_42〉. 〈inria-00098832〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

128