Efficient Algorithm for Constructing Order K Voronoi Diagrams in Road Networks
0
Citation
27
Reference
10
Related Paper
Abstract:
The order k Voronoi diagram (OkVD) is an effective geometric construction to partition the geographical space into a set of Voronoi regions such that all locations within a Voronoi region share the same k nearest points of interest (POIs). Despite the broad applications of OkVD in various geographical analysis, few efficient algorithms have been proposed to construct OkVD in real road networks. This study proposes a novel algorithm consisting of two stages. In the first stage, a new one-to-all k shortest path finding procedure is proposed to efficiently determine the shortest paths to k nearest POIs for each node. In the second stage, a new recursive procedure is introduced to effectively divide boundary links within different Voronoi regions using the hierarchical tessellation property of the OkVD. To demonstrate the applicability of the proposed OkVD construction algorithm, a case study of place-based accessibility evaluation is carried out. Computational experiments are also conducted on five real road networks with different sizes, and results show that the proposed OkVD algorithm performed significantly better than state-of-the-art algorithms.Keywords:
Centroidal Voronoi tessellation
Weighted Voronoi diagram
Tessellation (computer graphics)
Power diagram
Voronoi diagram is a method of partitioning a space, which has powerful potential in many fields. This paper presents two regular Voronoi diagrams: line weighted Voronoi diagram and area weighted Voronoi diagram. Owing to the difficulty of constructing regular Voronoi diagram based on vector method, it develops a raster based approach, which employs the Arc/Info, to compute a few regular Voronoi diagrams. Our programs can construct the following Voronoi diagrams: the ordinary Voronoi diagram, line Voronoi diagram, area Voronoi diagram, and the multiplicatively or additively or compoundly weighted Voronoi diagram generated by points or any figures(lines or polygons), in the plane. As there are a huge amount of grids, computing time in constructing line or polygon weighted Voronoi diagram is a bit more, and this problem is just the future research effort. Lastly, it makes an attempt to apply ordinary Voronoi diagram and weighted Voronoi diagram for delimitating city's affected coverage in Henan province whose experimental result shows that weighted Voronoi diagram is an efficient technique for delimitating economic object's affected coverage.
Centroidal Voronoi tessellation
Weighted Voronoi diagram
Power diagram
Polygon (computer graphics)
Cite
Citations (6)
Centroidal Voronoi tessellation
Power diagram
Weighted Voronoi diagram
Cite
Citations (79)
Weighted Voronoi diagrams are extensions of Voronoi diagrams.The area of weighted Voronoi region is an important property of a weighted Voronoi diagram.A computational method for the area of a weighted Voronoi region is proposed.With this method,for given generating points and weight,the attribute data of any weighted Voronoi arc between two acmes on the boundary of Voronoi regions could be obtained.The obtained data of every closed region are then stored in a circular linked list.The area of any weighted Voronoi region could be calculated according to the data stored in the lists.
Centroidal Voronoi tessellation
Weighted Voronoi diagram
Power diagram
Cite
Citations (0)
Tessellation (computer graphics)
Laguerre polynomials
Weighted Voronoi diagram
Centroidal Voronoi tessellation
Cite
Citations (4)
Given a point set the Voronoi diagram associates to each point all the locations in a plane that are closer to it . This diagram is often used in spatial analysis to divide an area among points. In the ordinary Voronoi diagram the points are treated as equals and the division is done in a purely geometrical way. A weighted Voronoi diagram is defined as an extension of the original diagram. The weight given usually relates to some variable property of the phenomenon represented by each point. The weighted distance is then computed as a function that depends both on the weight and on the euclidean distance. This article de- scribes a multiplicatively weighted Voronoi diagram implementation as an open source plugin for TerraView. The algorithm used computes an approximation of the diagram using multipolygons to represent each point's area. This choice avoids the voids that might appear in most of the implementations that focus on finding the intersections and scales well in memory.
Weighted Voronoi diagram
Power diagram
Centroidal Voronoi tessellation
Cite
Citations (1)
We developed a two-scan algorithm for discrete Voronoi tessellations of digital images. The computation time of our method is independent of the number of Voronoi sites. In addition to the previous additively, multiplicatively, compoundly weighted Voronoi diagrams and the additively weighted power Voronoi diagram, we proposed a new weighted Voronoi diagram, namely the compoundly weighted power Voronoi diagram. These five weighted Voronoi diagrams were efficiently computed with our two-scan algorithm.
Centroidal Voronoi tessellation
Power diagram
Weighted Voronoi diagram
Cite
Citations (1)
Centroidal Voronoi tessellation
Weighted Voronoi diagram
Power diagram
Medial axis
Cite
Citations (72)
In this thesis, a new generalized Voronoi diagram in the plane, called a bounded Voronoi diagram, is defined. This generalization is one of the natural extensions of the previously existing Voronoi diagrams in the plane. Three important cases of bounded Voronoi diagrams are discussed. They are: (1) The bounded Voronoi diagram for a monotone chain. (2) The bounded Voronoi diagram for a simple polygon. (3) The bounded Voronoi diagram for a set of non-crossing line segments.
Algorithms for constructing these bounded Voronoi diagrams are presented. All of them are optimal.
Bounded Voronoi diagrams are powerful tools which help to efficiently solve many geometric problems.
Centroidal Voronoi tessellation
Power diagram
Weighted Voronoi diagram
Polygon (computer graphics)
Cite
Citations (0)
The Voronoi diagram of connected domain is widely used. The generally adopted algorithms, such as divide-and-conquer method, are difficult to realize. A new method to establish free boundary connected domain Voronoi diagram is introduced based on the algorithm for determining the medial axis of an convex polygon. Through finding the bisectors of neighboring boundary elements, points of intersection of neighboring bisectors are obtained.Point of intersection with the minimum distance is used to realize the growing of Voronoi diagram. The entire simply-connected domain Voronoi diagram is established in this way. The Voronoi diagram merging algorithm for inner and outer boundary of multi-connected domain is also introduced.
Power diagram
Centroidal Voronoi tessellation
Weighted Voronoi diagram
Polygon (computer graphics)
Cite
Citations (0)
Weighted Voronoi diagram
Power diagram
Centroidal Voronoi tessellation
Polygon (computer graphics)
Computational Geometry
Cite
Citations (9)