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

DOI10.1137/S0097539795285916MaRDI QIDQ4210159zbMATH OpenFDO

Authors

Publication date 21 September 1998

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

zbMATH Keywords

algorithmcomputational geometryVoronoi diagrampolygonconstrained Delaunay triangulation

Mathematics Subject Classification ID

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

Recommendations

• Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time
• Constrained Delaunay triangulations
• A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON
• Two simple algorithms for constructing a two-dimensional constrained Delaunay triangulation

Cites work

• scientific article; zbMATH DE number 4064506 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Duality of constrained Voronoi diagrams and Delaunay triangulations
• Efficiently updating constrained Delaunay triangulations
• Generalized Delaunay triangulation for planar graphs
• Triangulating a simple polygon in linear time

Cited in

(12)

• Splitting a Delaunay triangulation in linear time
• Essential constraints of edge-constrained proximity graphs
• Two simple algorithms for constructing a two-dimensional constrained Delaunay triangulation
• Delaunay triangulation of imprecise points in linear time after preprocessing
• Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time
• Fast segment insertion and incremental construction of constrained Delaunay triangulations
• Optimizing Data Intensive Flows for Networks on Chips
• Shortcut hulls: vertex-restricted outer simplifications of polygons
• Construction of the nearest neighbor embracing graph of a point set
• Enumerating constrained non-crossing minimally rigid frameworks
• Computing hereditary convex structures
• Essential Constraints of Edge-Constrained Proximity Graphs

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

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