Locked and Unlocked Polygonal Chains in Three Dimensions |
| |
| Authors: | T. Biedl E. Demaine M. Demaine S. Lazard A. Lubiw J. O'Rourke M. Overmars S. Robbins I. Streinu G. Toussaint S. Whitesides |
| |
| Affiliation: | (1) Department of Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 {biedl, eddemaine, mldemaine, alubiw}@uwaterloo.ca, CA;(2) INRIA Lorraine, Villers-les-Nancy Cedex 54602, France lazard@loria.fr, FR;(3) Department of Computer Science, Smith College, Northampton, MA 01063, USA {orourke, streinu}@cs.smith.edu, US;(4) Department of Computer Science, Utrecht University, 3508 TB Utrecht, The Netherlands markov@cs.ruu.nl, NL;(5) School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2K6 {stever, godfried, sue}@cs.mcgill.ca, CA |
| |
| Abstract: | 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.' Received October 9, 1999, and in revised form February 6, 2001, and April 26, 2001. Online publication August 28, 2001. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
