Convexifying Monotone Polygons

Therese C. Biedl 1 Erik D. Demaine 1 Sylvain Lazard 2 Steven M. Robbins 3 Michael A. Soss 3
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
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

INRIA | LORIA | UNIV-LORRAINE

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

173

Téléchargements de fichiers

131

Contact


archive-ouverte@inria.fr