Duality of constrained Voronoi diagrams and Delaunay triangulations |
| |
| Authors: | Barry Joe Cao An Wang |
| |
| Affiliation: | (1) Department of Computing Science, University of Alberta, T6G 2H1 Edmonton, Alberta, Canada;(2) Present address: Department of Computer Science, Memorial University of Newfoundland, A1C 5S7 St. John's, Newfoundland, Canada |
| |
| Abstract: | We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.This work was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. |
| |
| Keywords: | Voronoi diagram Delaunay triangulation Duality Computational geometry |
| 本文献已被 SpringerLink 等数据库收录！ |
|
