Computational geometry in a curved world

DOI10.1007/BF01840397zbMath0696.68101OpenAlexW2040904149MaRDI QIDQ911324

Diane L. Souvaine, David P. Dobkin

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryconvex hull computationintersection detectioncurve algorithmdiameter decompositionkernel computationmonotonicity testingsplinegonsplinehedron

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Convex sets in (2) dimensions (including convex curves) (52A10) Polytopes and polyhedra (52Bxx)

Related Items

Detection and computation of conservative kernels of models consisting of freeform curves and surfaces, using inequality constraints, On determining optimal strategies in pursuit games in the plane, A Polynomial-Time Algorithm for Computing Shortest Paths of Bounded Curvature Amidst Moderate Obstacles, A tight bound for point guards in piecewise convex art galleries, An algorithmic approach to some problems in terrain navigation, Computing grasp functions, \(\alpha\)-kernel problem with fuzzy visibility, Visibility graphs, dismantlability, and the cops and robbers game, Kernel-based construction operators for Boolean sum and ruled geometry, On computing the convex hull of (piecewise) curved objects, Guarding curvilinear art galleries with vertex or point guards, Multi UAV coordination for tracking the dispersion of a contaminant cloud in an urban region, Detecting the intersection of convex objects in the plane, COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION, Linear-time algorithms for weakly-monotone polygons, Shortest curves in planar regions with curved boundary, Arc fibrations of planar domains, Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs, Representing planar domains by polar parameterizations with parabolic parameter lines, On determining optimal strategies in pursuit games in the plane, Minimizing Distance-to-Sight in Polygonal Domains, Computing an \(L_1\) shortest path among splinegonal obstacles in the plane, An exact and efficient approach for computing a cell in an arrangement of quadrics, An Output-Sensitive Convex Hull Algorithm for Planar Objects

Cites Work

• Fast detection of polyhedral intersection
• Decomposition and intersection of simple splinegons
• Detecting the intersection of convex objects in the plane
• A linear algorithm for determining the separation of convex polyhedra
• Curve Fitting with Conic Splines
• Triangulating Simple Polygons and Equivalent Problems
• Optimal Point Location in a Monotone Subdivision
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• Convex hulls of piecewise-smooth Jordan curves
• A Separator Theorem for Planar Graphs
• Optimal Search in Planar Subdivisions
• An Optimal Algorithm for Finding the Kernel of a Polygon
• Sorting jordan sequences in linear time using level-linked search trees
• Finding the convex hull of a simple polygon
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item