• Locked and Unlocked Polygonal...

Treffer: Locked and Unlocked Polygonal Chains in Three Dimensions

Title:
Locked and Unlocked Polygonal Chains in Three Dimensions
Authors:
Biedl, Thérèse, Demaine, Erik, Demaine, Martin, Lazard, Sylvain, Lubiw, Anna, O'Rourke, Joseph, Overmars, M., Robbins, Steve, Streinu, Ileana, Toussaint, Godfried, Whitesides, Sue
Contributors:
University of Waterloo [Waterloo], Models, algorithms and geometry for computer graphics and vision (ISA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science, SMITH COLLEGE, Departments of Psychonomics, and Media and Communication, Utrecht University (UTRECHT UNIVERSITY), Universiteit Utrecht / Utrecht University [Utrecht], McGill University = Université McGill [Montréal, Canada]
Source:
Symposium on Discrete Algorithms - SODA'99. :866-867
Publisher Information:
CCSD; ACM-SIAM, 1999.
Publication Year:
1999
Collection:
collection:CNRS
collection:INRIA
collection:INPL
collection:INRIA-LORRAINE
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:INRIA-ETATSUNIS
collection:INRIA-CANADA
collection:AM2I-UL
Subject Terms:
linkages, mécanismes articulés, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.0: General, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, [INFO.INFO-OH]Computer Science [cs], Other [cs.OH]
Subject Geographic:
Baltimore, United States
Original Identifier:
HAL:
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Access URL:
https://inria.hal.science/inria-00098772
https://inria.hal.science/inria-00098772v2/document
https://inria.hal.science/inria-00098772v2/file/99-R-227.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00098772v2
Database:
HAL

Weitere Informationen

This paper studies movements of polygonal chains in three dimensions whose links are not allowed to cross or change length. Our main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Other results include an algorithm for straightening open chains having a simple orthogonal projection onto some plane, and an algorithm for making convex any open chain initially configured on the surface of a polytope. All our algorithms require only O(n) basic ''moves.''