Voronoi diagrams—a survey of a fundamental geometric data structure

By Franz Aurenhammer. 1991

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Deep Reinforcement Learning for Swarm Systems (2018, background): “For comparison, the complexity of calculating Voronoi regions for the pursuit evasion policy scales O(N logN) with the number of agents (Aurenhammer, 1991).”
PolyMesher: a general-purpose mesh generator for polygonal elements written in Matlab (2012, background): “The properties of Voronoi diagrams have been studied extensively and we refer the reader to review paper (Aurenhammer 1991) on the topic.”
Advancements in continuous approximation models for logistics and transportation systems: 1996–2016 (2017, methodology): “Voronoi diagrams in combination with CA models can be useful in solving continuous location-districting problems; see Aurenhammer (1991) for a review on Voronoi Diagrams.”
Polygonal finite elements for topology optimization: A unifying paradigm (2010, background): “These diagrams have been studied extensively in mathematics, computer science, and natural sciences, and the interested reader is referred to [12] for a survey on the topic.”
Theta*: Any-Angle Path Planning on Grids (2007, background): “ be improved by simply increasing the grid resolution. We now list some alternative terrain discretizations, assuming for simplicity that the obstacles in the terrain are polygonal. • Voronoi graphs (Aurenhammer, 1991) discretize the terrain by biasing paths away from blocked polygons. The resulting”
Planning algorithms (2006, methodology): “For a survey on algorithms that compute Voronoi diagrams, see [55].”
Energy-efficient deployment of Intelligent Mobile sensor networks (2005, background): “Many researchers have demonstrated the importance and usefulness of VDs in various fields, such as mathematics, computational geometry, biology, chemistry, geography, communications, and coding theory [1], [29].”
The farthest point strategy for progressive image sampling (1994, background): “Further information regarding the VD may be found in [2] and [20].”
Approximate Nearest Neighbor Search Small World Approach (2011, methodology): “In order for the result of the algorithm to be the exact nearest element to the query, the network should contain the Delaunay graph as its subgraph, which is dual to the Voronoi tessellation [9].”
Data structures and algorithms for nearest neighbor search in general metric spaces (1993, methodology): “More recently, the Voronoi digram [21] has provided a useful tool in low- dimensional Euclidian settings { and Figure 1: vp-tree decomposition Figure 2: kd-tree decomposition the overall eld and outlook of Computational Geometry has yielded many interesting results such as those of [22, 23, 24, 25] ”
Wireless Communication Using Unmanned Aerial Vehicles (UAVs): Optimal Transport Theory for Hover Time Optimization (2017, methodology): “ed to one UAV, and the users within the cell partition must be serviced by the corresponding UAV. We note that, in classical cell partitioning approaches such as Voronoi and weighted Voronoi diagrams [25], the spatial distribution of users is not taken into account. As a result, some partitions can ”
Worst and best-case coverage in sensor networks (2005, background): “Furthermore, coverage formulations can try to find weak points in a sensor field and suggest future .”
Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces (2012, methodology): “There is a subset of shortrange links, which are used as an approximation of the Delaunay graph[8] required by the Greedy Search algorithm.”
A Linear Time Algorithm for Computing Exact Euclidean Distance Transforms of Binary Images in Arbitrary Dimensions (2003, unknown): “; nS [2], [29].”
Edwards Statistical Mechanics for Jammed Granular Matter (2016, unknown): “This defines the Voronoi tesselation, first introduced by the Ukrainian mathematician G. F. Voronoi in 1908, which is now widely used in mathematics and many applied areas (Aurenhammer, 1991; Okabe et al., 2000).”
Geometric Approximation Algorithms (2011, methodology): “Vornoi diagrams are a powerful tool and have numerous applications [Aur91].”
Distributed Control of Robotic Networks (2009, methodology): “The survey [Aurenhammer, 1991] and the book [Okabe et al.”
Dynamic clustering for acoustic target tracking in wireless sensor networks (2003, background): “As the locations of sensors are static (only subject to environmental factors such as wind), the intersection area can be determined in advance in the form of Voronoi diagram.”