Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Polygonal Chains Cannot Lock In 4d, Roxana Cocan, Joseph O'Rourke
Polygonal Chains Cannot Lock In 4d, Roxana Cocan, Joseph O'Rourke
Computer Science: Faculty Publications
We prove that, in all dimensions d ≥ 4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be achieved by algorithms that use polynomial time in the number of vertices, and result in a polynomial number of “moves.” These results contrast to those known for d = 2, where trees can “lock,” and for d = 3, where open and closed chains can lock.
Computational Geometry Column 42, Joseph S. B. Mitchell, Joseph O'Rourke
Computational Geometry Column 42, Joseph S. B. Mitchell, Joseph O'Rourke
Computer Science: Faculty Publications
A compendium of thirty previously published open problems in computational geometry is presented.
Computational Geometry Column 41, Joseph O'Rourke
Computational Geometry Column 41, Joseph O'Rourke
Computer Science: Faculty Publications
The recent result that n congruent balls in Rd have at most 4 distinct geometric permutations is described.