Name
Abstract | ||
|---|---|---|
In this paper we discuss the kinetic maintenance of the Euclidean Voronoi diagram and its dual, the Delaunay triangulation, for a set of moving disks. The most important aspect in our approach is that we can maintain the Voronoi diagram even in the case of intersecting disks. We achieve that by augmenting the Delaunay triangulation with some edges associated with the disks that do not contribute to the Voronoi diagram. Using the augmented Delaunay triangulation of the set of disks as the underlying structure, we discuss how to maintain, as the disks move, (1) the closest pair, (2) the connectivity of the set of disks and (3) in the case of non-intersecting disks, the near neighbors of a disk. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-44634-6_7 | WADS |
Keywords | Field | DocType |
euclidean voronoi diagram,closest pair,delaunay triangulation,augmented delaunay triangulation,intersecting disk,near neighbor,important aspect,voronoi diagrams,kinetic maintenance,voronoi diagram,disks move,kinetics | Topology,Power diagram,Combinatorics,Bowyer–Watson algorithm,Computer science,Weighted Voronoi diagram,Voronoi diagram,Constrained Delaunay triangulation,Closest pair of points problem,Delaunay triangulation,Pitteway triangulation | Conference |
Volume | ISSN | ISBN |
2125 | 0302-9743 | 3-540-42423-7 |
Citations | PageRank | References |
7 | 0.47 | 13 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Menelaos I. Karavelas | 1 | 229 | 18.99 |