Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time

DOI10.1137/S0097539795285916zbMath0915.68027MaRDI QIDQ4210159

No author found.

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

algorithmpolygonVoronoi diagramcomputational geometryconstrained Delaunay triangulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Data structures (68P05)

Related Items (9)

Optimizing Data Intensive Flows for Networks on Chips ⋮ Shortcut hulls: vertex-restricted outer simplifications of polygons ⋮ Enumerating constrained non-crossing minimally rigid frameworks ⋮ Construction of the nearest neighbor embracing graph of a point set ⋮ Computing hereditary convex structures ⋮ Essential Constraints of Edge-Constrained Proximity Graphs ⋮ Essential Constraints of Edge-Constrained Proximity Graphs ⋮ Delaunay triangulation of imprecise points in linear time after preprocessing ⋮ Fast segment insertion and incremental construction of constrained Delaunay triangulations

Cites Work

• Efficiently updating constrained Delaunay triangulations
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Generalized Delaunay triangulation for planar graphs
• Triangulating a simple polygon in linear time
• Duality of constrained Voronoi diagrams and Delaunay triangulations
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time