Detecting and decomposing self-overlapping curves

DOI10.1016/0925-7721(92)90019-OMaRDI QIDQ1200911zbMATH OpenOpenAlexFDO

Authors Christopher J. Van Wyk, Peter W. Shor

Publication date 16 January 1993

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(92)90019-o

zbMATH Keywords

closed plane curvedynamic programmingself- intersectionsself-overlapping curve

Mathematics Subject Classification ID

Differential geometry of immersions (minimal, prescribed curvature, tight, etc.) (53C42) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

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.

Recommendations

• Self-overlapping curves revisited
• Combinatorial properties of self-overlapping curves and interior boundaries
• Selfintersection of composite curves and surfaces
• Detecting the intersection of convex objects in the plane
• A linear time and space algorithm for detecting path intersection

Cites work

• Detecting and decomposing self-overlapping curves
• Differentiable approximations to light interior transformations
• Extensions of Normal Immersions of S 1 into R 2
• Generalized Delaunay triangulation for planar graphs
• scientific article; zbMATH DE number 3481526 (Why is no real title available?)
• scientific article; zbMATH DE number 3228674 (Why is no real title available?)
• scientific article; zbMATH DE number 3354296 (Why is no real title available?)
• Rectilinear planar layouts and bipolar orientations of planar graphs
• The combinatorial topology of analytic functions on the boundary of a disk
• The Folded Ribbon Theorem. A Contribution to the Study of Immersed Circles

Cited in

(12)

• Detecting regions with undesirable curvature
• Detecting and decomposing self-overlapping curves
• Selfintersection of composite curves and surfaces
• A general method for decomposing self-intersecting polygon to normal based on self-intersection points
• Counting hexagonal patches and independent sets in circle graphs
• Combinatorial properties of self-overlapping curves and interior boundaries
• Cusps of Characteristic Curves and Intersection-Aware Visualization of Path and Streak Lines
• Self-overlapping curves revisited
• From curves to words and back again: geometric computation of minimum-area homotopy
• Wilson loop expectations as sums over surfaces on the plane
• Finding a shortest curve that separates few objects from many
• An isoperimetric inequality in the universal cover of the punctured plane

This page was built for publication: Detecting and decomposing self-overlapping curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1200911)