Paper by Erik D. Demaine
- Erik D. Demaine and Sarah Eisenstat, “Expansive Motions for d-Dimensional Open Chains”, in Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, Ontario, Canada, August 10–12, 2011, to appear.
We consider the problem of straightening chains in d ≥ 3
dimensions, possibly embedded into higher dimensions, using expansive motions.
For any d ≥ 3, we show that there is an open chain in d dimensions that
is not straight and not self-touching yet has no expansive motion.
Furthermore, for any Δ > 0 and d ≥ 3, we show that there is an
open chain in d dimensions that cannot be straightened using expansive
motions when embedded into ℝd × [−Δ, Δ] (a bounded
extra dimension). On the positive side, we prove that any open chain in
d ≥ 2 dimensions can be straightened using an expansive motion when embedded
into ℝd + 1 (a full extra dimension).
- The paper is 6 pages.
- The paper is available in PDF (308k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 3, 2017 by