Name
Title | ||
|---|---|---|
A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains |
Abstract | ||
|---|---|---|
We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O..nC k/ log.nC k// where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O.nC k/. Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L1 metric. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/PL00009199 | Algorithmica |
Keywords | Field | DocType |
Key words. Geodesic Voronoi diagrams,Shortest paths,Polygon triangulation,Topological plane sweep,Computational geometry. | Power diagram,Discrete mathematics,Combinatorics,Polygonal number,Voronoi diagram,Simple polygon,Polygonal modeling,Star-shaped polygon,Polygonal chain,Polygon triangulation,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 4 | 0178-4617 |
Citations | PageRank | References |
18 | 0.97 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evanthia Papadopoulou | 1 | 110 | 18.37 |
| D. T. Lee | 2 | 18 | 0.97 |