Detecting and decomposing self-overlapping curves (Q1200911)

Let \(C\) be a closed curve (= point set which is homeomorphic to the unit circle \(S^ 1\)) in the real Euclidean plane. \(C\) is called self- overlapping if it can be divided by nontrivial line segments into simple (closed) curves. The authors give an algorithm for recognizing if \(C\) --- which is assumed to have a finite number of \(k\) self-intersections and may be a polygon or a general closed curve --- is self-overlapping. This algorithm is based on ``triangulating'' a self-overlapping polygon by using dynamic programming and will run in \(O(k^ 6)\) time, in general. Besides, several interesting topological properties of self-overlapping curves are described and applications (robotics, analysis of integrated- circuit layouts) are mentioned.