Name
Title | ||
|---|---|---|
Efficient Computation of the Geodesic Voronoi Diagram of Points in a Simple Polygon (Extended Abstract) |
Abstract | ||
|---|---|---|
We present an O((n+k) log(n+k)) time algorithm for computing the geodesic Voronoi diagram of k points in a simple polygon of n vertices improving upon the previously known results. The method introduces a new approach to the construction of geodesic Voronoi diagrams by combining a sweep of the polygon and the merging step of a usual divide-and-conquer strategy. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-60313-1_147 | ESA |
Keywords | Field | DocType |
efficient computation,extended abstract,geodesic voronoi diagram,simple polygon,voronoi diagram,divide and conquer | Power diagram,Discrete mathematics,Combinatorics,Centroidal Voronoi tessellation,Computer science,Mathematical diagram,Weighted Voronoi diagram,Voronoi diagram,Simple polygon,Geodesic,Computation | Conference |
ISBN | Citations | PageRank |
3-540-60313-1 | 4 | 0.48 |
References | Authors | |
11 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evanthia Papadopoulou | 1 | 110 | 18.37 |
| D. T. Lee | 2 | 2418 | 1083.30 |