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.     

Applications of random sampling to on-line algorithms in computational geometry

This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space and time complexities when averaging over all permutations of the input data. The method is general and can be applied to various geometric problems. The power of the technique is illustrated by new efficient on-line algorithms for constructing convex hulls and Voronoi diagrams in any dimension, Voronoi diagrams of line segments in the plane, arrangements of curves in the plane, and others. This work has been supported in part by the ESPRIT Basic Research Action Nr. 3075 (ALCOM).     

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 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.

Voronoi cells via linear inequality systems

The theory and methods of linear algebra are a useful alternative to those of convex geometry in the framework of Voronoi cells and diagrams, which constitute basic tools of computational geometry. As shown by Voigt and Weis in 2010, the Voronoi cells of a given set of sites T, which provide a tesselation of the space called Voronoi diagram when T is finite, are solution sets of linear inequality systems indexed by T. This paper exploits systematically this fact in order to obtain geometrical information on Voronoi cells from sets associated with T (convex and conical hulls, tangent cones and the characteristic cones of their linear representations). The particular cases of T being a curve, a closed convex set and a discrete set are analyzed in detail. We also include conclusions on Voronoi diagrams of arbitrary sets.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

Solving some vector subset problems by Voronoi diagrams

We propose a general approach to solving some vector subset problems in a Euclidean space that is based on higher-order Voronoi diagrams. In the case of a fixed space dimension, this approach allows us to find optimal solutions to these problems in polynomial time which is better than the runtime of available algorithms.     

Abstract Voronoi diagrams revisited

Abstract Voronoi diagrams [R. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, vol. 400, Springer-Verlag, 1987] were designed as a unifying concept that should include as many concrete types of diagrams as possible. To ensure that abstract Voronoi diagrams, built from given sets of bisecting curves, are finite graphs, it was required that any two bisecting curves intersect only finitely often; this axiom was a cornerstone of the theory. In [A.G. Corbalan, M. Mazon, T. Recio, Geometry of bisectors for strictly convex distance functions, International Journal of Computational Geometry and Applications 6 (1) (1996) 45–58], Corbalan et al. gave an example of a smooth convex distance function whose bisectors have infinitely many intersections, so that it was not covered by the existing AVD theory. In this paper we give a new axiomatic foundation of abstract Voronoi diagrams that works without the finite intersection property.     

Aspects of the Facet-Edge Data Structure for the Construction of Voronoi Cells

The construction of Voronoi diagrams has two main aspects: The construction algorithm and the data structure. For the construction of planar Voronoi diagrams e.g. the well known plane sweep algorithm can be applied. Another efficient method is the incremental construction of the Delaunay triangulation by using the quad-edge data structure. Within this data structure the Delaunay triangulation is treated as a planar graph. Incremental construction implies that manipulations of the triangulation are allowed. Its Voronoi diagram is obtained simply by accessing the triangulation's dual graph. We extend this method to tree dimensions, by implementing a 3D Delaunay triangulation on the facet-edge data structure. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

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.     

Improved algorithms for discs and balls using power diagrams

The properties of a particular generalization of Voronoi diagrams called power diagrams are exploited to obtain new and improved algorithms for union, intersection, and measure problems for discs and balls.     

Zone diagrams in compact subsets of uniformly convex normed spaces

A zone diagram is a relatively new concept which has emerged in computational geometry and is related to Voronoi diagrams. Formally, it is a fixed point of a certain mapping, and neither its uniqueness nor its existence are obvious in advance. It has been studied by several authors, starting with T. Asano, J. Matoušek and T. Tokuyama, who considered the Euclidean plane with singleton sites, and proved the existence and uniqueness of zone diagrams there. In the present paper we prove the existence of zone diagrams with respect to finitely many pairwise disjoint compact sites contained in a compact and convex subset of a uniformly convex normed space, provided that either the sites or the convex subset satisfy a certain mild condition. The proof is based on the Schauder fixed point theorem, the Curtis-Schori theorem regarding the Hilbert cube, and on recent results concerning the characterization of Voronoi cells as a collection of line segments and their geometric stability with respect to small changes of the corresponding sites. Along the way we obtain the continuity of the Dom mapping as well as interesting and apparently new properties of Voronoi cells.     

2D Centroidal Voronoi Tessellations with Constraints

<正>We tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation.We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges.The clipping itself is efficiently computed by identifying for each constrained edge the(connected) set of triangles whose dual Voronoi vertices are hidden by the constraint.The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints.     

Quickest Paths, Straight Skeletons, and the City Voronoi Diagram

The city Voronoi diagram is induced by quickest paths in the L ₁plane, made faster by an isothetic transportation network. We investigate the rich geometric and algorithmic properties of city Voronoi diagrams, and report on their use in processing quickest-path queries. In doing so, we revisit the fact that not every Voronoi-type diagram has interpretations in both the distance model and the wavefront model. Especially, straight skeletons are a relevant example where an interpretation in the former model is lacking. We clarify the relationship between these models, and further draw a connection to the bisector-defined abstract Voronoi diagram model, with the particular goal of computing the city Voronoi diagram efficiently.     

The Voronoi Diagram of Curved Objects

Voronoi diagrams of curved objects can show certain phenomena that are often considered artifacts: The Voronoi diagram is not connected; there are pairs of objects whose bisector is a closed curve or even a two-dimensional object; there are Voronoi edges between different parts of the same site (so-called self-Voronoi-edges); these self-Voronoi-edges may end at seemingly arbitrary points not on a site, and, in the case of a circular site, even degenerate to a single isolated point. We give a systematic study of these phenomena, characterizing their differential-geometric and topological properties. We show how a given set of curves can be refined such that the resulting curves define a “well-behaved” Voronoi diagram. We also give a randomized incremental algorithm to compute this diagram. The expected running time of this algorithm is O(n log n).     

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.     

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.     

Tropical Bisectors and Voronoi Diagrams

Foundations of Computational Mathematics - In this paper we initiate the study of tropical Voronoi diagrams. We start out with investigating bisectors of finitely many points with respect to...     

Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.