Splitting a Delaunay triangulation in linear time

DOI10.1007/s00453-002-0939-8zbMath1016.68137OpenAlexW1972369894MaRDI QIDQ1849762

Olivier Devillers, Mercè Mora, Bernard Chazelle, Ferran Hurtado, Vera Sacristán

Publication date: 1 December 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-002-0939-8

zbMATH Keywords

computational geometryrandomized algorithmsDelaunay triangulationVoronoi diagrams

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (8)

Delaunay Triangulation of Imprecise Points Simplified and Extended ⋮ Three problems about simple polygons ⋮ Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance ⋮ Preprocessing imprecise points for Delaunay triangulation: simplified and extended ⋮ A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations ⋮ A tight lower bound for computing the diameter of a 3D convex polytope ⋮ Spanning trees in multipartite geometric graphs ⋮ Computing hereditary convex structures

This page was built for publication: Splitting a Delaunay triangulation in linear time