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

DOI10.1137/S0097539795285916zbMATH Open0915.68027MaRDI QIDQ4210159FDOQ4210159

Authors:

Publication date: 21 September 1998

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

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

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)

Cites Work

• Title not available (Why is that?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Triangulating a simple polygon in linear time
• Generalized Delaunay triangulation for planar graphs
• Duality of constrained Voronoi diagrams and Delaunay triangulations
• Efficiently updating constrained Delaunay triangulations
• Title not available (Why is that?)

Cited In (12)

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

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)