Robust Computation of 3D Apollonius Diagrams

Apollonius diagrams, also known as additively weighted Voronoi diagrams, are an extension of Voronoi diagrams, where the weighted distance is defined by the Euclidean distance minus the weight. The bisectors of Apollonius diagrams have a hyperbolic form, which is fundamentally different from traditional Voronoi diagrams and power diagrams. Though robust solvers are available for computing 2D Apollonius diagrams, there is no practical approach for the 3D counterpart. In this paper, we systematically analyze the structural features of 3D Apollonius diagrams, and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D. Our algorithm consists of vertex location, edge tracing and face extraction, among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex. Finally, we use centroidal Voronoi tessellation (CVT) to discretize the curved bisectors with well-tessellated triangle meshes. We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments. We also demonstrate an application on computing centroidal Apollonius diagram.     

Polyline‐sourced Geodesic Voronoi Diagrams on Triangle Meshes

This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line‐segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n‐face mesh with m generators, where N = max{m, n}. Computational results on real‐world models demonstrate the efficiency of our algorithm.     

Sorting helps for voronoi diagrams

It is well known that, using standard models of computation, Ω(n logn) time is required to build a Voronoi diagram forn point sites. This follows from the fact that a Voronoi diagram algorithm can be used to sort. However, if the sites are sorted before we start, can the Voronoi diagram be built any faster? We show that for certain interesting, although nonstandard, types of Voronoi diagrams, sorting helps. These nonstandard types of Voronoi diagrams use a convex distance function instead of the standard Euclidean distance. A convex distance function exists for any convex shape, but the distance functions based on polygons (especially triangles) lead to particularly efficient Voronoi diagram algorithms. Specifically, a Voronoi diagram using a convex distance function based on a triangle can be built inO (n log logn) time after initially sorting then sites twice. Convex distance functions based on other polygons require more initial sorting.     

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations

The combinatorial complexities of (1) the Voronoi diagram of moving points in 2D and (2) the Voronoi diagram of lines in 3D, both under the Euclidean metric, continues to challenge geometers because of the open gap between the Ω(n²) lower bound and the O(n3+?) upper bound. Each of these two combinatorial problems has a closely related problem involving Minkowski sums: (1′) the complexity of a Minkowski sum of a planar disk with a set of lines in 3D and (2′) the complexity of a Minkowski sum of a sphere with a set of lines in 3D. These Minkowski sums can be considered “cross-sections” of the corresponding Voronoi diagrams. Of the four complexity problems mentioned, problems (1′) and (2′) have recently been shown to have a nearly tight bound: both complexities are O(n2+?) with lower bound Ω(n²).In this paper, we determine the combinatorial complexities of these four problems for some very simple input configurations. In particular, we study point configurations with just two degrees of freedom (DOFs), exploring both the Voronoi diagrams and the corresponding Minkowski sums. We consider the traditional versions of these problems to have 4 DOFs. We show that even for these simple configurations the combinatorial complexities have upper bounds of either O(n²) or O(n2+?) and lower bounds of Ω(n²).     

A simple GPU-based approach for 3D Voronoi diagram construction and visualization

In this paper we propose a simple GPU-based approach for discrete incremental approximation of 3D Voronoi diagram. By constructing region maps via GPU. Nearest sites, space clustering, and shortest distance query can be quickly answered by looking up the region map. In addition, we propose another representation of the 3D Voronoi diagram for visualization.     

Order-k voronoi diagrams of sites with additive weights in the plane

It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k?2)(n?k) vertices, (6k?3)(n?k) edges, and (2k?1)(n?itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k ² n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.     

基于动态创建局部Voronoi图的连续近邻查询

在充分认识到k阶Voronoi图在解决连续k个近邻查询优越性和现实不可行性的基础上,用分支限界的思想去界定预创建Voronoi图生成点范围的上界,提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。该方法只是在给定查询段上所有点的k个近邻范围上界内创建一个局部的k阶Voronoi图,这样大大降低了基于Voronoi图的连续k近邻查询的代价。     

Approximation of fruit skin patterns using spherical Voronoi diagrams

In nature, there are many tessellation patterns on curved surfaces that look like Voronoi diagrams. Typical examples are the patterns found on fruit skins. Verifying that a given tessellation is a Voronoi diagram will be useful for constructing mathematical models of polygonal patterns. However, the data are usually obtained as a 2D projected image, and hence it is not easy to compare it with a Voronoi diagram on a curved surfaces. We propose a framework for using a photograph of a fruit to measure the difference between the pattern on its skin and a spherical Voronoi diagram. The problem of finding the spherical Voronoi diagram that best fits the fruit skin pattern is reduced to an optimization problem. The validity of this formulation is evaluated using jackfruit and lychee. We also propose generalizations of our problem for further research.     

Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams

Let X = {f₁, …, f_n} be a set of scalar functions of the form f_i : ?² → ? which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered ε‐isotopic approximation of the minimization diagram of X. By exploiting soft predicates and clustering of Voronoi vertices, our algorithm is the first that can handle arbitrary degeneracies in X, and allow scalar functions which are piecewise smooth, and not necessarily semi‐algebraic. We apply these ideas to the computation of anisotropic Voronoi diagram of polygonal sets; this is a natural generalization of anisotropic Voronoi diagrams of point sites, which extends multiplicatively weighted Voronoi diagrams. We implement a prototype of our anisotropic algorithm and provide experimental results.     

三维限定Voronoi网格剖分细化算法

针对分段线性复合形约束条件下的三维限定Voronoi剖分问题,提出一种细化算法.首先证明了分段线性复合形中的元素在最终生成的三维限定Voronoi网格中可表示为Power图结构;受此启发,提出了对限定线段平面片分别进行一维二维Power图细化以实现三维限定Voronoi 网格生成的细化算法,并且证明了该算法对于任意分段线性复合形收敛.最后通过实例验证了文中算法的有效性.     

Exact Computation of the Topology and Geometric Invariants of the Voronoi Diagram of Spheres in 3D

In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu’s algorithm. Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu’s algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu’s algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.     

Order-k voronoi diagrams of sites with additive weights in the plane

It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k–2)(n–k) vertices, (6k–3)(n–k) edges, and (2k–1)(n–itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k ² n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.Work on this paper has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862.     

Restricting Voronoi diagrams to meshes using corner validation

Restricted Voronoi diagrams are a fundamental geometric structure used in many applications such as surface reconstruction from point sets or optimal transport. Given a set of sites V = { v _k}ⁿ_k=1 ? ?^d and a mesh X with vertices in ?^d connected by triangles, the restricted Voronoi diagram partitions X by computing for each site the portion of X for which the site is the nearest. The restricted Voronoi diagram is the intersection between the regular Voronoi diagram and the mesh. Depending on the site distribution or the ambient space dimension computing the regular Voronoi diagram may not be feasible using classical algorithms. In this paper, we extend Lévy and Bonneel's approach [ LB12 ] based on nearest neighbor queries. We show that their method is limited when the sites are not located on X . We propose a new algorithm for computing restricted Voronoi which reduces the number of sites considered for each triangle of the mesh and scales smoothly when the sites are far from the surface.     

Euclidean Voronoi diagram of 3D balls and its computation via tracing edges

Despite its important applications in various disciplines in science and engineering, the Euclidean Voronoi diagram for spheres, also known as an additively weighted Voronoi diagram, in 3D space has not been studied as much as it deserves. In this paper, we present an algorithm to compute the Euclidean Voronoi diagram for 3D spheres with different radii. The presented algorithm follows Voronoi edges one by one until the construction is completed in O(mn) time in the worst-case, where m is the number of edges in the Voronoi diagram and n is the number of spherical balls. As building blocks, we show that Voronoi edges are conics that can be precisely represented as rational quadratic Bézier curves. We also discuss how to conveniently represent and process Voronoi faces which are hyperboloids of two sheets.     

Some results on the computation of Voronoi diagrams on a mesh with multiple broadcasting

Voronoi diagram is one of the most fundamental and important geometric data structures. Voronoi diagram was historically defined for a set of points on the plane. The diagram partitions the plane into regions, one per site. The region of a site s consists of all points closer to s than to any other sites on the plane. Concepts of Voronoi diagram are often attributed to Voronoi (J. Reine Angew. Math. 133 (1907) 97) and Dirichlet (J. Reine Angew. Math. 40 (1850) 209). As a result of these early works, often the name Voronoi diagram and Dirichlet tessellation is used. Due to the importance of Voronoi diagrams, it is important that algorithms are devised to compute these structures in an efficient manner. Of course, this will create new opportunities for the applicability of these data structures. Towards this end, this paper presents new results for the computation of Voronoi diagrams for a set of n points, or n disjoint circles on the plane, on a mesh with multiple broadcasting (MMB) of size n×n. The algorithm runs in O(log² n) time.     

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to improve their approximations. Voronoi diagrams turn out to be useful for this approximation. Although it is known that Voronoi vertices for a sample of points from a curve in 2D approximate its medial axis, a similar result does not hold in 3D. Recently, it has been discovered that only a subset of Voronoi vertices converge to the medial axis as sample density approaches infinity. However, most applications need a nondiscrete approximation as opposed to a discrete one. To date no known algorithm can compute this approximation straight from the Voronoi diagram with a guarantee of convergence. We present such an algorithm and its convergence analysis in this paper. One salient feature of the algorithm is that it is scale and density independent. Experimental results corroborate our theoretical claims.     

分区加权Voronoi图的性质及其面积计算

分区加权Voronoi图是Voronoi图和加权Voronoi图的推广,可以用来模拟移动通信中基站发射天线分扇区以不同功率向周围发射时所覆盖区域的形状。首先,给出了分区加权Voronoi图的性质、定理及相关证明;其次,分析了分区加权Voronoi图中的各种区域,并给出了一种计算相应区域面积的算法;最后,利用分区加权Voronoi图模拟石家庄市部分城区中的基站建设情况,并对模拟产生的重复覆盖、服务区和盲区面积进行了计算。     

MapReduce模型下Voronoi图栅格生成算法

针对"海量"点组成的平面点集Voronoi图栅格生成算法的效率问题,对其进行易并行性抽象,提出了一种MapReduce模型下基于欧氏距离的Voronoi图栅格生成算法,该算法采用三个MapReduce Job来实现。在第一个MapReduce Job中,将栅格按照隶属代码进行归属分类。在第二个MapReduce Job中,将新数据按照其对应的行号进行归类。在第三个MapReduce Job中,并行生成全局有序的Voronoi图部分文件,并连接各个部分文件,生成最终的Voronoi图。在多个不同大小数据集上的实验结果表明,这种MapReduce模型下的算法部署在Hadoop集群上运行具有较好的加速比和扩展性。     

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to improve their approximations. Voronoi diagrams turn out to be useful for this approximation. Although it is known that Voronoi vertices for a sample of points from a curve in 2D approximate its medial axis, a similar result does not hold in 3D. Recently, it has been discovered that only a subset of Voronoi vertices converge to the medial axis as sample density approaches infinity. However, most applications need a nondiscrete approximation as opposed to a discrete one. To date no known algorithm can compute this approximation straight from the Voronoi diagram with a guarantee of convergence. We present such an algorithm and its convergence analysis in this paper. One salient feature of the algorithm is that it is scale and density independent. Experimental results corroborate our theoretical claims.     

The Hausdorff Voronoi Diagram of Point Clusters in the Plane

We study the Hausdorff Voronoi diagram of point clusters in the plane, a generalization ofVoronoi diagrams based on the Hausdorff distance function. We derive a tight combinatorial bound on the structural complexity of this diagram and present a plane sweep algorithm for its construction. In particular, we show that the size of the Hausdorff Voronoi diagram is (n + m), where n is the number of points on the convex hulls of the given clusters, and m is the number of crucial supporting segments between pairs of crossing clusters. The plane sweep algorithm generalizes the standard plane sweep paradigm for the construction of Voronoi diagrams with the ability to handle disconnected Hausdorff Voronoi regions. The Hausdorff Voronoi diagram finds direct application in the problem of computing the critical area of a VLSI layout, a measure reflecting the sensitivity of the VLSI design to spot defects during manufacturing.