A sweepline algorithm for Voronoi diagrams |
| |
Authors: | Steven Fortune |
| |
Affiliation: | (1) AT&T Bell Laboratories, 07974 Murray Hill, NJ, USA |
| |
Abstract: | We introduce a geometric transformation that allows Voronoi diagrams to be computed using a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms haveO(n logn) worst-case running time and useO(n) space. |
| |
Keywords: | Voroni diagram Delaunay triangulation Sweepline algorithm |
本文献已被 SpringerLink 等数据库收录! |
|