Paper Info
Title
Sphere-based Computation of Delaunay Diagrams on Points from 4d Grids
Abstract
The Delaunay diagram in d dimensions is the dual of the Voronoi diagram of a set of input sites. If we assume no degeneracies in the input, i.e. no d + 2 sites are co-spherical, then the diagram is a triangulation. Because this assumption is common, and can be enforced by symbolic perturbation, we often forget that Delaunay diagrams need not be triangulations. Input sets chosen from integer grids are common in scienti拢 c visualization applications, however, and these often have many degeneracies. Perturbation signi拢cantly increases the size of the Delaunay and dual Voronoi diagrams-a single 4D cube becomes 16 to 24 simplices, so one dual vertex becomes many. Our result is a sphere-based algorithm for direct, incremental computation of the Delaunay diagram in 4D. For input with many degeneracies, its speed is comparable to our fastest Delaunay triangulation program, yet it computes the exact Delaunay diagram.
Year
DOI
Venue
2006
10.1109/ISVD.2006.32
ISVD
Keywords
Field
DocType
symbolic perturbation,exact delaunay diagram,cantly increase,input site,delaunay diagram,sphere-based computation,incremental computation,perturbation signi,fastest delaunay triangulation program,dual vertex,voronoi diagram,delaunay diagrams,grid computing,interpolation,computational geometry,lifting equipment,data engineering,mesh generation,computational modeling,sampling methods,arithmetic,visualization,delaunay triangulation,computer science,data visualisation,scientific visualization
Discrete mathematics,Chew's second algorithm,Combinatorics,Bowyer–Watson algorithm,Triangulation (social science),Voronoi diagram,Constrained Delaunay triangulation,Mathematics,Ruppert's algorithm,Delaunay triangulation,Pitteway triangulation
Conference
ISBN
Citations 
PageRank 
0-7695-2630-6
0
0.34
References 
Authors
4
2
Name
Order
Citations
PageRank
Yuanxin Liu11239.27
Jack Snoeyink22842231.68