Please use this identifier to cite or link to this item:
標題: A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains
作者: E.Papadopoulou
關鍵字: Key words. Geodesic Voronoi diagrams, Shortest paths, Polygon triangulation, Topological plane sweep, Computational geometry.
出版社: Springer-Verlag
摘要: 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((n+k) log(n+k)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+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 L 1 metric.
ISSN: 0178-4617
Appears in Collections:資訊科學與工程學系所



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.