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.     

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.     

Delaunay meshing of isosurfaces

We present an isosurface meshing algorithm, DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three-dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three-dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation using a variety of volume datasets.     

Uncertain Voronoi diagram

In this paper, we introduce the fuzzy Voronoi diagram as an extension of the Voronoi diagram. We assume Voronoi sites to be fuzzy points and then define the Voronoi diagram for this kind of sites, then we provide an algorithm for computing this diagram based on Fortune's algorithm which costs O(nlogn) time. Also we introduce the fuzzy Voronoi diagram for a set of fuzzy circles, rather than fuzzy points, of the same radius. We prove that the boundary of this diagram is formed by the intersection of some hyperbolae, and finally we provide an O(n³logn)-time algorithm to compute the boundary.     

An optimal algorithm for constructing the weighted voronoi diagram in the plane

Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by d_e(x,p)/w(p) where d_e denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.An algorithm which constructs the weighted Voronoi diagram for S in O(n²) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n²) faces, edges and vertices.     

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.     

A sweepline algorithm for Voronoi diagrams

We introduce a geometric transformation that allows Voronoi diagrams to be computed using a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms haveO(n logn) worst-case running time and useO(n) space.     

On a Nearest-Neighbor Problem Under Minkowski and Power Metrics for Large Data Sets

The paper presents the sequential and the parallel algorithm for solving the nearest-neighbor problem in the plane, based on the generalized Voronoi diagram construction. The applications of the problem are found in the areas of networking, communications, distributed systems, computer modeling and information retrieval. The input for the problem is the set of circular sites S with varying radii, the query point p and the metric (Minkowski or power) according to which the site, neighboring the query point, is to be reported. The sequential algorithm takes O(n) time to build the data structure and O(log n) time for each query. The parallel algorithm requires O(log n log) preprocessing time and O(log) query time on EREW PRAM architecture with n/log n processors. The IDG/NNM software was developed for an experimental study of the problem. The experimental results demonstrate that the Voronoi diagram method outperforms the k – d tree method for all tested input configurations. The tests were conducted on large data sets, comprising thousands of generators.     

A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains

We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+k)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+k) . Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L ₁ metric. Received February 15, 1996; revised November 2, 1996.     

Computability of Partial Delaunay Triangulation and Voronoi Diagram [Extended Abstract]

Using the domain-theoretic model for geometric computation, we define the partial Delaunay triangulation and the partial Voronoi diagram of N partial points in R² and show that these operations are domain-theoretically computable and effectively computable with respect to Hausdorff distance and Lebesgue measure. These results are obtained by showing that the map which sends three partial points to the partial disc passing through them is computable. This framework supports the design of robust algorithms for computing the Delaunay triangulation and the Voronoi diagram with imprecise input.     

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.     

Computing the volume of the union of spheres

OnO(n ²) exact algorithm is given for computing the volume of a set ofn spheres in space. The algorithm employs the Laguerre Voronoi (power) diagram and a method for computing the volume of the intersection of a simplex and a sphere exactly. We give a new proof of a special case of a conjecture, popularized by Klee, concerning the change in volume as the centres of the spheres become further apart.     

AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations

TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL ₁ metric or theL _∞ metric.     

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.     

Implementing Shared Memory on Mesh-Connected Computers and on the Fat-Tree

We present deterministic upper and lower bounds on the slowdown required to simulate an (n, m)-PRAM on a variety of networks. The upper bounds are based on a novel scheme that exploits the splitting and combining of messages. This scheme can be implemented on an n-node d-dimensional mesh (for constant d) and on an n-leaf pruned butterfly and attains the smallest worst-case slowdown to date for such interconnections, namely, O(n^1/d(log(m/n))^1-1/d) for the d-dimensional mesh (with constant d) and O( ) for the pruned butterfly. In fact, the simulation on the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, we prove restricted and unrestricted lower bounds on the slowdown of any deterministic PRAM simulation on an arbitrary network, formulated in terms of the bandwidth properties of the interconnection as expressed by its decomposition tree.     

A sweepline algorithm for Voronoi diagrams

We introduce a geometric transformation that allows Voronoi diagrams to be computed using a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms haveO(n logn) worst-case running time and useO(n) space.     

Linear time Euclidean distance transform algorithms

Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed     

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图的顶点和边数的上界

多边形的Voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held证明了一个简单多边形的内部Voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中n和k分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其Voronoi图转化为有根树,并利用有根树的性质,给出了其内部Voronoi图的顶点和边数上界的估计,并对Voronoi区域的边界所包含顶点和边数的平均值进行了讨论."SDU数字博物馆"系统所采用的基于Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.