Decomposition and intersection of simple splinegons

DOI10.1007/BF01762127zbMath0648.68062OpenAlexW2051831392MaRDI QIDQ1105375

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

curvescomputational geometryconvex decompositionintersection detectionsplinegonmonotone decompositionsimplicity testing

Mathematics Subject Classification ID

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

Related Items

On determining optimal strategies in pursuit games in the plane, Fourth- and Higher-order Interface Tracking Via Mapping and Adjusting Regular Semianalytic sets Represented by Cubic Splines, A tight bound for point guards in piecewise convex art galleries, Computational geometry in a curved world, Multi UAV coordination for tracking the dispersion of a contaminant cloud in an urban region, 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, Computing an \(L_1\) shortest path among splinegonal obstacles in the plane

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposing a Polygon into Simpler Components
• Triangulation and shape-complexity
• Triangulating Simple Polygons and Equivalent Problems
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• Convex hulls of piecewise-smooth Jordan curves
• Optimal Search in Planar Subdivisions
• Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
• Location of a Point in a Planar Subdivision and Its Applications
• Decomposition of Polygons into Convex Sets
• Sorting jordan sequences in linear time using level-linked search trees