A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations

DOI10.1007/s00454-014-9629-yzbMath1302.68291arXiv1212.5098OpenAlexW2063055940MaRDI QIDQ471140

Donald R. Sheehy, Gary Lee Miller

Publication date: 14 November 2014

Published in: Discrete \& Computational Geometry, Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.5098

zbMATH Keywords

mesh generationVoronoi diagramoutput-sensitive algorithmsDelaunay triangulationkinetic data structures

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Combinatorial complexity of geometric structures (52C45)

Related Items

Unnamed Item, Randomized incremental construction of Delaunay triangulations of nice point sets, A novel method based on similarity and triangulation for predicting the toxicities of various binary mixtures

Cites Work

• Unnamed Item
• Unnamed Item
• Analytic solutions and conserved quantities of wave equation on torus
• Computing hereditary convex structures
• Properties of \(n\)-dimensional triangulations
• On the complexity of d-dimensional Voronoi diagrams
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Incremental convex hull algorithms are not output sensitive
• Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
• Nice point sets can have nasty Delaunay triangulations
• Output-sensitive results on convex hulls, extreme points, and related problems
• Splitting a Delaunay triangulation in linear time
• Incremental topological flipping works for regular triangulations
• Convex hulls, oracles, and homology
• Geometry and Topology for Mesh Generation
• Voronoi Diagrams and Delaunay Triangulations
• Finding the convex hull facet by facet
• On the Radius-Edge Condition in the Control Volume Method
• A fast algorithm for well-spaced points and approximate delaunay graphs
• Beating the spread
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• An Algorithm for Convex Polytopes