Decomposition and intersection of simple splinegons

DOI10.1007/BF01762127MaRDI QIDQ1105375zbMATH OpenOpenAlexFDO

Authors David P. Dobkin, Diane L. Souvaine, Christopher J. Van Wyk

Publication date 1988

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01762127

zbMATH Keywords

computational geometryconvex decompositioncurvesintersection detectionmonotone decompositionsimplicity testingsplinegon

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Analysis of algorithms and problem complexity (68Q25)

Review text

A splinegon is a polygon whose edges have been replaced by ``well- behaved curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.

Recommendations

• scientific article; zbMATH DE number 2197927
• Efficient intersection between splines of clothoids
• On computational aspects of simplicial splines
• scientific article; zbMATH DE number 1284030
• On discrete simplex splines and subdivision
• scientific article; zbMATH DE number 2020193
• scientific article; zbMATH DE number 4136677
• Approximate convex decomposition of polygons
• Approximate convex decomposition of polygons
• scientific article; zbMATH DE number 1361568

Cites work

• An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
• Convex hulls of piecewise-smooth Jordan curves
• Decomposing a Polygon into Simpler Components
• Decomposition of Polygons into Convex Sets
• Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
• scientific article; zbMATH DE number 3918300 (Why is no real title available?)
• scientific article; zbMATH DE number 3986641 (Why is no real title available?)
• scientific article; zbMATH DE number 4037201 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3219506 (Why is no real title available?)
• scientific article; zbMATH DE number 3232606 (Why is no real title available?)
• scientific article; zbMATH DE number 3063670 (Why is no real title available?)
• Location of a Point in a Planar Subdivision and Its Applications
• Optimal Search in Planar Subdivisions
• Sorting jordan sequences in linear time using level-linked search trees
• Triangulating Simple Polygons and Equivalent Problems
• Triangulation and shape-complexity

Cited in

(15)

• Triangulating a simple polygon in linear time
• Detecting the intersection of convex objects in the plane
• Tiling polygons with parallelograms
• Shortest curves in planar regions with curved boundary
• On determining optimal strategies in pursuit games in the plane
• A general method for decomposing self-intersecting polygon to normal based on self-intersection points
• Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
• A tight bound for point guards in piecewise convex art galleries
• Fourth- and higher-order interface tracking via mapping and adjusting regular semianalytic sets represented by cubic splines
• On determining optimal strategies in pursuit games in the plane
• Multi UAV coordination for tracking the dispersion of a contaminant cloud in an urban region
• Self-intersecting polygons resulting from contour evolution for shape similarity
• Efficient one-sided linearization of spline geometry
• Voronoi-based splinegon decomposition and shortest-path tree computation
• Computational geometry in a curved world

This page was built for publication: Decomposition and intersection of simple splinegons

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