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.     

Simulation of typical Cox–Voronoi cells with a special regard to implementation tests

We consider stationary Poisson line processes in the Euclidean plane and analyze properties of Voronoi tessellations induced by Poisson point processes on these lines. In particular, we describe and test an algorithm for the simulation of typical cells of this class of Cox–Voronoi tessellations. Using random testing, we validate our algorithm by comparing theoretical values of functionals of the zero cell to simulated values obtained by our algorithm. Finally, we analyze geometric properties of the typical Cox–Voronoi cell and compare them to properties of the typical cell of other well-known classes of tessellations, especially Poisson–Voronoi tessellations. Our results can be applied to stochastic–geometric modelling of networks in telecommunication and life sciences, for example. The lines can then represent roads in urban road systems, blood arteries or filament structures in biological tissues or cells, while the points can be locations of telecommunication equipment or vesicles, respectively.     

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.     

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.     

Locating waste pipelines to minimize their impact on marine environment

A waste pipeline, considered as an undesirable facility, is to be located in a coastal region. Two criteria are taken into account, the Euclidean distance from a given set of protected areas (coral reefs and sandbanks) and a utility function related to the pipe length, both to be maximized. The paper describes a methodology to obtain an efficient set of points where the extreme of a marine pipeline should be located. Since the formulation of the model is based on the zone Voronoi diagram, the computational complexity of the solving procedure is low.     

Approximations of a Ginzburg-Landau model for superconducting hollow spheres based on spherical centroidal Voronoi tessellations

In this paper the numerical approximations of the Ginzburg- Landau model for a superconducting hollow spheres are constructed using a gauge invariant discretization on spherical centroidal Voronoi tessellations. A reduced model equation is used on the surface of the sphere which is valid in the thin spherical shell limit. We present the numerical algorithms and their theoretical convergence as well as interesting numerical results on the vortex configurations. Properties of the spherical centroidal Voronoi tessellations are also utilized to provide a high resolution scheme for computing the supercurrent and the induced magnetic field.

     

Truncated Newton-Based Multigrid Algorithm for Centroidal Voronoi Diagram Calculation

In a variety of modern applications there arises a need to tessellate the domain into representative regions, called Voronoi cells. A particular type of such tessellations, called centroidal Voronoi tessellations or CVTs, are in big demand due to their optimality properties important for many applications. The availability of fast and reliable algorithms for their construction is crucial for their successful use in practical settings. This paper introduces a new multigrid algorithm for constructing CVTs that is based on the MG/Opt algorithm that was originally designed to solve large nonlinear optimization problems. Uniform convergence of the new method and its speedup comparing to existing techniques are demonstrated for linear and nonlinear densities for several 1d and 2d problems, and $O(k)$ complexity estimation is provided for a problem with $k$ generators.     

AN UPPER BOUND ON AVERAGE TOUCHING NUMBER OF A VORONOI PARTITION

A Voronoi partition is decided bythe configurations of N centerepoints in n dimensional Euclidean space. The total number of nearest neighbor points for a given centerpoint in the partition is called its touching number. It is shown that the average touching number for all points in a Voronoi partition is not greater than the n dimensional kissing number, that is, the maximum uumber of unit spheres that can touch a given unit sphere without overlapping.     

Minimax Bounds in Nonparametric Estimation of Multidimensional Deterministic Dynamical Systems

We consider the problem of estimating a multidimensional discrete deterministic dynamical system from the first n + 1 observations. We exhibit the optimal rate function r _n and show that the nearest neighbor estimator achieves this optimal rate, extending a recent study carried out by Guerre and Maës [18] in the univariate case. Previous results strongly rely on the natural order structure of the set of real numbers. Here the optimal rate function is defined from multidimensional spacings which are edge lengths of simplices associated with a triangulation of the Voronoi cells built from the observations. A simulated example illustrates the theory.     

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.     

Simulation Studies of Some Voronoi Point Processes

We introduce a new class of dynamic point process models with simple and intuitive dynamics that are based on the Voronoi tessellations generated by the processes. Under broad conditions, these processes prove to be ergodic and produce, on stabilisation, a wide range of clustering patterns. In the paper, we present results of simulation studies of three statistical measures (Thiel’s redundancy, van Lieshout and Baddeley’s J-function and the empirical distribution of the Voronoi nearest neighbours’ numbers) for inference on these models from the clustering behaviour in the stationary regime. In particular, we make comparisons with the area-interaction processes of Baddeley and van Lieshout.     

Cooperative Sensing and Distributed Control of a Diffusion Process Using Centroidal Voronoi Tessellations

<正>This paper considers how to use a group of robots to sense and control a diffusion process.The diffusion process is modeled by a partial differential equation (PDE),which is a both spatially and temporally variant system.The robots can serve as mobile sensors,actuators,or both.Centroidal Voronoi Tessellations based coverage control algorithm is proposed for the cooperative sensing task.For the diffusion control problem,this paper considers spraying control via a group of networked mobile robots equipped with chemical neutralizers,known as smart mobile sprayers or actuators,in a domain of interest having static mesh sensor network for concentration sensing.This paper also introduces the information sharing and consensus strategy when using centroidal Voronoi tessellations algorithm to control a diffusion process.The information is shared not only on where to spray but also on how much to spray among the mobile actuators.Benefits from using CVT and information consensus seeking for sensing and control of a diffusion process are demonstrated in simulation results.     

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.

Edge-Weighted Centroidal Voronoi Tessellations

<正>Most existing applications of centroidal Voronoi tessellations(CVTs) lack consideration of the length of the cluster boundaries.In this paper we propose a new model and algorithms to produce segmentations which would minimize the total energy—a sum of the classic CVT energy and the weighted length of cluster boundaries.To distinguish it with the classic CVTs,we call it an Edge-Weighted CVT(EWCVT).The concept of EWCVT is expected to build a mathematical base for all CVT related data classifications with requirement of smoothness of the cluster boundaries.The EWCVT method is easy in implementation,fast in computation,and natural for any number of clusters.     

Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay

In the 1920s, B. N. Delaunay proved that the dual graph of the Voronoi diagram of a discrete set of points in a Euclidean space gives rise to a collection of simplices, whose circumspheres contain no points from this set in their interior. Such Delaunay simplices tessellate the convex hull of these points. An equivalent formulation of this property is that the characteristic functions of the Delaunay simplices form a partition of unity. In the paper this result is generalized to the so-called Delaunay configurations. These are defined by considering all simplices for which the interiors of their circumspheres contain a fixed number of points from the given set, in contrast to the Delaunay simplices, whose circumspheres are empty. It is proved that every family of Delaunay configurations generates a partition of unity, formed by the so-called simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the well-known univariate B-splines. It is also shown that the linear span of the simplex splines contains all algebraic polynomials of degree not exceeding the degree of the splines.

     

A comparison of several nearest neighbor classifier metrics using Tabu Search algorithm for the feature selection problem

The feature selection problem is an interesting and important topic which is relevant for a variety of database applications. This paper utilizes the Tabu Search metaheuristic algorithm to implement a feature subset selection procedure while the nearest neighbor classification method is used for the classification task. Tabu Search is a general metaheuristic procedure that is used in order to guide the search to obtain good solutions in complex solution spaces. Several metrics are used in the nearest neighbor classification method, such as the euclidean distance, the Standardized Euclidean distance, the Mahalanobis distance, the City block metric, the Cosine distance and the Correlation distance, in order to identify the most significant metric for the nearest neighbor classifier. The performance of the proposed algorithms is tested using various benchmark datasets from UCI Machine Learning Repository.     

Asymptotics for Statistical Distances Based on Voronoi Tessellations

We obtain an information-type inequality and a strong law for a wide class of statistical distances between empirical estimates and random measures based on Voronoi tessellations. This extends some basic results in the asymptotic theory of sample spacings, when the cells of the Voronoi tessellation are interpreted as d-dimensional spacings.     

Advances in Studies and Applications of Centroidal Voronoi Tessellations

<正>Centroidal Voronoi tessellations(CVTs) have become a useful tool in many applications ranging from geometric modeling,image and data analysis,and numerical partial differential equations,to problems in physics,astrophysics,chemistry,and biology. In this paper,we briefly review the CVT concept and a few of its generalizations and well-known properties.We then present an overview of recent advances in both mathematical and computational studies and in practical applications of CVTs.Whenever possible,we point out some outstanding issues that still need investigating.     

Percolation on random Johnson–Mehl tessellations and related models

We make use of the recent proof that the critical probability for percolation on random Voronoi tessellations is 1/2 to prove the corresponding result for random Johnson–Mehl tessellations, as well as for two-dimensional slices of higher-dimensional Voronoi tessellations. Surprisingly, the proof is a little simpler for these more complicated models. B. Bollobás’s research was supported in part by NSF grants CCR-0225610 and DMS-0505550 and ARO grant W911NF-06-1-0076. O. Riordan’s research was supported by a Royal Society Research Fellowship.