A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations
From MaRDI portal
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
mesh generationVoronoi diagramoutput-sensitive algorithmsDelaunay triangulationkinetic data structures
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