




















A hinged-ruler is a sequence of line segments in the plane joined end-to-end with hinges, so each hinge joins exactly two segments, the first segment and last segment are adjacent to only one hinge each, and all other segments are adjacent to exactly two hinges. Hopcroft, Joseph, and Whitesides first posed the hinged-ruler-folding problem in their 1985 paper "On the Movement of Robot Arms in 2-Dimensional Bounded Regions": given a hinged-ruler and a real number $K$, can the hinged-ruler be folded so as to fit within a one-dimensional interval of length $K$? We show that if the segment lengths are constrained to be real numbers in the interval $[0,1]$, then we can always fold the hinged-ruler so as to fit within a one-dimensional interval of length $2-Ω(\frac{1}{2^{n/4}})$. On the other hand, we give a construction for a hinged-ruler which cannot be folded into some one-dimensional interval of length $2-O(\frac{1}{2^{n/4}})$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。