We define a plane curve to be threadable if it can rigidly pass through a point-hole in a line L without otherwise touching L. Threadable curves are in a sense generalizations of monotone curves. Our main result is a linear-time algorithm for deciding whether a polygonal curve is threadable, and if so, finding a sequence of rigid motions to thread it through a hole. In addition, we sketch arguments that show that the threadability of algebraic curves can be decided in time polynomial in the degree of the curve , and that threading a 3D polygonal curve through a point-hole in a plane can be decided in quadratic time. Finally, we connect threadable curves to the problem known as "moving a chair through a doorway."
We define a plane curve to be threadable if it can rigidly pass through a point-hole in a line L without otherwise touching L. Threadable curves are in a sense generalizations of monotone curves. We have two main results. The first is a linear-time algorithm for deciding whether a polygonal curve is threadable---O(n) for a curve of n vertices---and if threadable, finding a sequence of rigid motions to thread it through a hole. We also sketch an argument that shows that the threadability of algebraic curves can be decided in time polynomial in the degree of the curve . The second main result is an O(n polylog n)-time algorithm for deciding whether a 3D polygonal curve can thread through hole in a plane in R^3, and if so, providing a description of the rigid motions that achieve the threading.
R
Our main result
We have two main results. The first
R
threadable, and if so,
threadable---O(n) for a curve of n vertices---and if threadable,
R
In addition, we sketch arguments that show
We also sketch an argument that shows
R
, and that threading
. The second main result is an O(n polylog n)-time algorithm for deciding whether
R
through a point-hole
can thread through hole
R
can be decided in quadratic time. Finally, we connect threadable curves to the problem known as "moving a chair through a doorway."
in R^3, and if so, providing a description of the rigid motions that achieve the threading.