Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog³n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region.     

A linear-time algorithm for computing the voronoi diagram of a convex polygon

We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram ofn sites in the plane can be computed in (n) time when these sites form the vertices of a convex polygon in, say, counterclockwise order. This settles an open problem in computational geometry. Our techniques can also be used to obtain linear-time algorithms for computing the furthest-site Voronoi diagram and the medial axis of a convex polygon and for deleting a site from a general planar Voronoi diagram.This research began while the first and fourth authors were visiting the Mathematical Sciences Research Institute in Berkeley, California. Work by the fourth author was supported in part by NSF Grant No. 8120790.     

Dynamization of order decomposable set problems

Order decomposable set problems are introduced as a general class of problems concerning sets of multidimensional objects. We give a method of structuring sets such that the answer to an order decomposable set problem can be maintained with low worst-case time bounds, while objects are inserted and deleted in the set. Examples include the maintenance of the two-dimensional Voronoi diagram of a set of points, and of the convex hull of a three-dimensional point set in linear time. We show that there is a strong connection between the general dynamization method given and the well-known technique of divide-and-conquer used for solving many problems concerning static sets of objects. Although the upper bounds obtained are low in order of magnitude, the results do not necessarily imply the existence of fast feasible update routines. Hence the results merely assess theoretical bounds for the various set problems considered.     

Bregman Voronoi Diagrams

The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define various variants of Voronoi diagrams depending on the class of objects, the distance function and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g., k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connection with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation.     

A Fast Robust Algorithm for Computing Discrete Voronoi Diagrams

We describe an algorithm for the construction of discretized Voronoi diagrams on a CPU within the context of a large scale numerical fluid simulation. The Discrete Voronoi Chain (DVC) algorithm is fast, flexible and robust. The algorithm stores the Voronoi diagram on a grid or lattice that may be structured or unstructured. The Voronoi diagram is computed by alternatively updating two lists of grid cells per particle to propagate a growth boundary of cells from the particle locations. Distance tests only occur when growth boundaries from different particles collide with each other, hence the number of distance tests is effectively minimized. We give some empirical results for two and three dimensions. The method generalizes to any dimension in a straight forward manner. The distance tests can be based any metric.     

Randomized incremental construction of simple abstract Voronoi diagrams in 3-space

We introduce the simple abstract Voronoi diagram in 3-space as an abstraction of the usual Voronoi diagram. We show that the 3-dimensional simple abstract Voronoi diagram of n sites can be computed in O(n²) expected time using O(n²) expected space by a randomized algorithm. The algorithm is based on the randomized incremental construction technique of Clarkson and Shor (1989). We apply the algorithm to some concrete types of such diagrams: power diagrams, diagrams under ellipsoid convex distance functions, and diagrams under the Hausdorff distance for sites that are parallel segments all having the same length.     

Voronoi diagram and medial axis algorithm for planar domains with curved boundaries — II: Detailed algorithm description

Details of algorithms to construct the Voronoi diagrams and medial axes of planars domain bounded by free-form (polynomial or rational) curve segments are presented, based on theoretical foundations given in the first installment Ramamurthy and Farouki, J. Comput. Appl. Math. (1999) 102 119–141 of this two-part paper. In particular, we focus on key topological and computational issues that arise in these constructions. The topological issues include: (i) the data structures needed to represent various geometrical entities — bisectors, Voronoi regions, etc., and (ii) the Boolean operations (i.e., union, intersection, and difference) on planar sets required by the algorithm. Specifically, representations for the Voronoi polygons of boundary segments, and for individual Voronoi diagram or medial axis edges, are proposed. Since these edges may be segments of (a) nonrational algebraic curves (curve/curve bisectors); (b) rational curves (point/curve bisectors); or (c) straight lines (point/point bisectors), data structures tailored to each of these geometrical entities are introduced. The computational issues addressed include the curve intersection algorithms required in the Boolean operations, and iterative schemes used to precisely locate bifurcation or “n-prong” points (n ⩾ 3) of the Voronoi diagram and medial axis. A selection of computed Voronoi diagram and medial axis examples is included to illustrate the capabilities of the algorithm.     

Computing Voronoi skeletons of a 3-D polyhedron by space subdivision

We tackle the problem of computing the Voronoi diagram of a 3-D polyhedron whose faces are planar. The main difficulty with the computation is that the diagram's edges and vertices are of relatively high algebraic degrees. As a result, previous approaches to the problem have been non-robust, difficult to implement, or not provenly correct.

We introduce three new proximity skeletons related to the Voronoi diagram: (1) the Voronoi graph (VG), which contains the complete symbolic information of the Voronoi diagram without containing any geometry; (2) the approximate Voronoi graph (AVG), which deals with degenerate diagrams by collapsing sub-graphs of the VG into single nodes; and (3) the proximity structure diagram (PSD), which enhances the VG with a geometric approximation of Voronoi elements to any desired accuracy. The new skeletons are important for both theoretical and practical reasons. Many applications that extract the proximity information of the object from its Voronoi diagram can use the Voronoi graphs or the proximity structure diagram instead. In addition, the skeletons can be used as initial structures for a robust and efficient global or local computation of the Voronoi diagram.

We present a space subdivision algorithm to construct the new skeletons, having three main advantages. First, it solves at most uni-variate quartic polynomials. This stands in sharp contrast to previous approaches, which require the solution of a non-linear tri-variate system of equations. Second, the algorithm enables purely local computation of the skeletons in any limited region of interest. Third, the algorithm is simple to implement.     

Voronoi diagram and medial axis algorithm for planar domains with curved boundaries I. Theoretical foundations

In this first installment of a two-part paper, the underlying theory for an algorithm that computes the Voronoi diagram and medial axis of a planar domain bounded by free-form (polynomial or rational) curve segments is presented. An incremental approach to computing the Voronoi diagram is used, wherein a single boundary segment is added to an existing boundary-segment set at each step. The introduction of each new segment entails modifying the Voronoi regions of the existing boundary segments, and constructing the Voronoi region of the new segment. We accomplish this by (i) computing the bisector of the new segment with each of the current boundary segments; (ii) updating the Voronoi regions of the current boundary segments by partitioning them with these bisectors; and (iii) constructing the Voronoi region of the new segment as a union of regions obtained from the partitioning in (ii). When all boundary segments are included, and their Voronoi regions have been constructed, the Voronoi diagram of the boundary is obtained as the union of the Voronoi polygons for each boundary segment. To construct the medial axis of a planar domain, we first compute the Voronoi diagram of its boundary. The medial axis is then obtained from the Voronoi diagram by (i) removing certain edges of the Voronoi diagram that do not belong to the medial axis, and (ii) adding certain edges that do belong to the medial axis but are absent from the Voronoi diagram; unambiguous characterizations for edges in both these categories are given. Details of algorithms based on this theory are deferred to the second installment of this two-part paper.     

On the construction of abstract voronoi diagrams

We show that the abstract Voronoi diagram ofn sites in the plane can be constructed in timeO(n logn) by a randomized algorithm. This yields an alternative, but simpler,O(n logn) algorithm in many previously considered cases and the firstO(n logn) algorithm in some cases, e.g., disjoint convex sites with the Euclidean distance function. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein [13]. Our algorithm is based on Clarkson and Shor's randomized incremental construction technique [7]. This work was supported by the DFG, Me 620/6, and ESPRIT P3075 ALCOM. A preliminary version of this paper has been presented at STACS '90, Rouen, France.     

Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.

An efficient algorithm for the three-dimensional diameter problem

We explore a new approach for computing the diameter of n points in \Bbb R ³ that is based on the restriction of the furthest-point Voronoi diagram to the convex hull. We show that the restricted Voronoi diagram has linear complexity. We present a deterministic algorithm with O(nlog ² n) running time. The algorithm is quite simple and is a good candidate to be implemented in practice. Using our approach the chromatic diameter and all-furthest neighbors in \Bbb R ³ can be found in the same running time. Received February 18, 2000, and in revised form June 27, 2000. Online publication January 17, 2001.     

A New Approach to Output-Sensitive Construction of Voronoi Diagrams and Delaunay Triangulations

We describe a new algorithm for computing the Voronoi diagram of a set of \(n\) points in constant-dimensional Euclidean space. The running time of our algorithm is \(O(f \log n \log \varDelta )\) where \(f\) is the output complexity of the Voronoi diagram and \(\varDelta \) is the spread of the input, the ratio of largest to smallest pairwise distances. Despite the simplicity of the algorithm and its analysis, it improves on the state of the art for all inputs with polynomial spread and near-linear output size. The key idea is to first build the Voronoi diagram of a superset of the input points using ideas from Voronoi refinement mesh generation. Then, the extra points are removed in a straightforward way that allows the total work to be bounded in terms of the output complexity, yielding the output sensitive bound. The removal only involves local flips and is inspired by kinetic data structures.     

Locational optimization problems solved through Voronoi diagrams

This paper reviews a class of continuous locational optimization problems (where an optimal location or an optimal configuration of facilities is found in a continuum on a plane or a network) that can be solved through the Voronoi diagram. Eight types of continuous locational optimization problems are formulated, and these problems are solved through the ordinary Voronoi diagram, the farthest-point Voronoi diagram, the weighted Voronoi diagram, the network Voronoi diagram, the Voronoi diagram with a convex distance function, the line Voronoi diagram, and the area Voronoi diagram.     

On the minimum corridor connection problem and other generalized geometric problems

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.     

Vesicle computers: Approximating a Voronoi diagram using Voronoi automata

Irregular arrangements of vesicles filled with excitable and precipitating chemical systems are imitated by Voronoi automata - finite-state machines defined on a planar Voronoi diagram. Every Voronoi cell takes four states: resting, excited, refractory and precipitate. A resting cell excites if it has at least one neighbour in an excited state. The cell precipitates if the ratio of excited cells in its neighbourhood versus the number of neighbours exceeds a certain threshold. To approximate a Voronoi diagram on Voronoi automata we project a planar set onto the automaton lattice, thus cells corresponding to data-points are excited. Excitation waves propagate across the Voronoi automaton, interact with each other and form precipitate at the points of interaction. The configuration of the precipitate represents the edges of an approximated Voronoi diagram. We discover the relationship between the quality of the Voronoi diagram approximation and the precipitation threshold, and demonstrate the feasibility of our model in approximating Voronoi diagrams of arbitrary-shaped objects and in constructing a skeleton of a planar shape.     

Stable marker-particle method for the Voronoi diagram in a flow field

The Voronoi diagram in a flow field is a tessellation of water surface into regions according to the nearest island in the sense of a “boat-sail distance”, which is a mathematical model of the shortest time for a boat to move from one point to another against the flow of water. The computation of the diagram is not easy, because the equi-distance curves have singularities. To overcome the difficulty, this paper derives a new system of equations that describes the motion of a particle along the shortest path starting at a given point on the boundary of an island, and thus gives a new variant of the marker-particle method. In the proposed method, each particle can be traced independently, and hence the computation can be done stably even though the equi-distance curves have singular points.     

Voronoi diagrams and arrangements

We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR ^d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems.