Aspect-ratio Voronoi diagram and its complexity bounds

This Letter first defines an aspect ratio of a triangle by the ratio of the longest side over the minimal height. Given a set of line segments, any point p in the plane is associated with the worst aspect ratio for all the triangles defined by the point and the line segments. When a line segment si gives the worst ratio, we say that p is dominated by si. Now, an aspect-ratio Voronoi diagram for a set of line segments is a partition of the plane by this dominance relation. We first give a formal definition of the Voronoi diagram and give O(n2+ε) upper bound and Ω(n²) lower bound on the complexity, where ε is any small positive number. The Voronoi diagram is interesting in itself, and it also has an application to a problem of finding an optimal point to insert into a simple polygon to have a triangulation that is optimal in the sense of the aspect ratio.     

移动点Voronoi图拓扑维护策略的研究

移动环境下基于Voronoi图的最近邻查询必须要解决随时间不断改变的移动点Voronoi图的拓扑结构的维护问题。通过一组离散的,有限的事件序列对其对偶图Delaunay图拓扑改变过程的模拟来实现对移动点Voronoi图拓扑结构的维护。把带有事件驱动机制的移动数据结构（Kinetic Data Structure,KDS）模型作为移动点的运动模型,给出了KDS模型对其对偶图Delaunay图拓扑结构改变维护的具体策略,并对移动环境下动态插入或删除移动点时Voronoi图的拓扑维护问题进行了研究。最后给出了移动环境下基于Voronoi图的近邻查询的数据库实现模型。     

Higher-order Voronoi diagrams on triangulated surfaces

We study the complexity of higher-order Voronoi diagrams on triangulated surfaces under the geodesic distance, when the sites may be polygonal domains of constant complexity. More precisely, we show that on a surface defined by n triangles the sum of the combinatorial complexities of the order-j Voronoi diagrams of m sites, for j=1,…,k, is O(k²n²+k²m+knm), which is asymptotically tight in the worst case.     

Voronoi diagrams with barriers and on polyhedra for minimal path planning

Two generalizations of the Voronoi diagram in two dimensions (E²) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.This material is based upon work supported by the National Science Foundation under grants ECS-8021504 and ECS-8351942. The second author is also supported in part by a Fulbright scholarship     

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.     

Voronoi Diagram for services neighboring a highway

We are given a transportation line where displacements happen at a bigger speed than in the rest of the plane. A shortest time path is a path between two points which takes less than or equal time to any other. We consider the time to follow a shortest time path to be the time distance between the two points. In this paper, we give a simple algorithm for computing the Time Voronoi Diagram, that is, the Voronoi Diagram of a set of points using the time distance.     

Duality of constrained Voronoi diagrams and Delaunay triangulations

We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.This work was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

Ready, Set, Go! The Voronoi diagram of moving points that start from a line

It is an outstanding open problem of computational geometry to prove a near-quadratic upper bound on the number of combinatorial changes in the Voronoi diagram of points moving at a common constant speed along linear trajectories in the plane. In this note we observe that this quantity is Θ(n²) if the points start their movement from a common line.     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

“The big sweep”: On the power of the wavefront approach to Voronoi diagrams

We show that the wavefront approach to Voronoi diagrams (a deterministic line-sweep algorithm that does not use geometric transform) can be generalized to distance measures more general than the Euclidean metric. In fact, we provide the first worst-case optimal (O (n logn) time,O(n) space) algorithm that is valid for the full class of what has been callednice metrics in the plane. This also solves the previously open problem of providing anO (nlogn)-time plane-sweep algorithm for arbitraryL _k -metrics. Nice metrics include all convex distance functions but also distance measures like the Moscow metric, and composed metrics. The algorithm is conceptually simple, but it copes with all possible deformations of the diagram. Research partially supported by the Natural Sciences and Engineering Research Council of Canada. Research partially supported by the Deutsche Forschungsgemeinschaft, Grant No. Kl 655/2-1.     

Using geometry to solve the transportation problem in the plane

LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦=, andn=k+. These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n^2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the ₁ metric, the ₂ metric, and the metric. The running time for the ₁ and metrics can be improved to 0(n²(logn)³ logN).D. S. Atkinson was supported by the National Science Foundation under Grant CCR90-57481PYI. P. M. Vaidya was supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

Voronoi tessellation of points with integer coordinates: Time-efficient implementation and online edge-list generation

The Voronoi tessellation in the plane can be computed in a particularly time-efficient manner for generators with integer coordinates, such as typically acquired from a raster image. The Voronoi tessellation is constructed line by line during a single scan of the input image, simultaneously generating an edge-list data structure (DCEL) suitable for postprocessing by graph traversal algorithms. In contrast to the generic case, it can be shown that the topology of the grid permits the algorithm to run faster on complex scenes. Consequently, in Computer Vision applications, the computation of the Voronoi tessellation represents an attractive alternative to raster-based techniques in terms of both computational complexity and quality of data structures.     

Voronoi diagrams of polygons: A framework for shape representation

This paper describes an efficient shape representation framework for planar shapes using Voronoi skeletons.This paper makes the following significant contributions. First a new algorithm for the construction of the Voronoi diagram of a polygon with holes is described. The main features of this algorithm are its robustness in handling the standard degenerate cases (colinearity of more than two points; co-circularity of more than three points), and its ease of implementation. It also features a robust numerical scheme to compute non-linear parabolic edges that avoids having to solve equations of degree greater than two. The algorithm has been fully implemented and tested in a variety of test inputs.Second, the Voronoi diagram of a polygon is used to derive accurate and robust skeletons for planar shapes. The shape representation scheme using Voronoi skeletons possesses the important properties of connectivity as well as Euclidean metrics. Redundant skeletal edges are deleted in a pruning step which guarantees that connectivity of the skeleton will be preserved. The resultant representation is stable with respect to being invariant to perturbations along the boundary of the shape. A number of examples of shapes with and without holes are presented to demonstrate the features of this approach.     

A parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping

This paper presents a parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping. The binary tree splitting method is used to adaptively group the point set in the plane and construct sub‐Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in each group consumes the majority of time and that construction within one group does not affect that in other groups, the use of a parallel algorithm is suitable. After constructing the sub‐Voronoi diagrams, we extracted the boundary points of the four sides of each sub‐group and used to construct boundary site Voronoi diagrams. Finally, the sub‐Voronoi diagrams containing each boundary point are merged with the corresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experiments demonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function of the size of the point set, the number of processors, the average number of points in each block, and the number of boundary points. Copyright © 2013 John Wiley & Sons, Ltd.     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。     

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.     

On the geodesic voronoi diagram of point sites in a simple polygon

Given a simple polygon withn sides in the plane and a set ofk point sites in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal geodesic distance inside the polygon as the metric. We describe anO((n + k) log(n + k) logn)-time algorithm for solving this problem and sketch a fasterO((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.Work on this paper was performed while the author held an AT&T Bell Laboratories Ph.D. Scholarship at New York University.     

Settling the bound on the rectilinear link radius of a simple rectilinear polygon

We improve the best known bound on the rectilinear link radius of a simple rectilinear polygon with respect to its rectilinear link diameter. The new bound is tight and is compatible with the known bound on the (regular) link radius of a (regular) simple polygon with respect to its (regular) link diameter. The previous bound on the rectilinear link radius of a simple rectilinear polygon was proven by Nilsson and Schuierer in 1991.     

Proximity problems for points on a rectilinear plane with rectangular obstacles

We consider the following four problems for a setS ofk points on a plane, equipped with the rectilinear metric and containing a setR ofn disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles inR): (a) find aclosest pair of points inS, (b) find anearest neighbor for each point inS, (c) compute the rectilinearVoronoi diagram ofS, and (d) compute a rectilinearminimal spanning tree ofS. We describeO ((n+k) log(n+k))-time sequential algorithms for (a) and (b) based onplane-sweep, and the consideration of geometrically special types of shortest paths, so-calledz-first paths. For (c) we present anO ((n+k) log(n+k) logn)-time sequential algorithm that implements a sophisticateddivide-and-conquer scheme with an addedextension phase. In the extension phase of this scheme we introduce novel geometric structures, in particular so-calledz-diagrams, and techniques associated with the Voronoi diagram. Problem (d) can be reduced to (c) and solved inO ((n+k) log(n+k) logn) time as well. All our algorithms arenear-optimal, as well as easy to implement. An extended abstract appeared inProc. 13th Conf. on the Foundations of Software Technology and Theoretical Computer Science, Bombay, 1993, Springer-Verlag, pp. 218–227. Sumanta Guha was supported in part by a UW-Milwaukee Graduate School Research Committee Award. Ichiro Suzuki was supported in part by the National Science Foundation under Grants CCR-9004346 and IRI-9307506, the Office of Naval Research under Grant N00014-94-1-0284, and an endowed chair supported by Hitachi Ltd. at the Faculty of Engineering Science, Osaka University.     

A Randomized Algorithm for the Voronoi Diagram of Line Segments on Coarse-Grained Multiprocessors

We present a randomized algorithm for computing the Voronoi diagram of line segments using coarse-grained parallel machines. Operating on P processors, for any input of n line segments, this algorithm performs O((n log n)/P) local operations per processor, O(n/P) messages per processor, and O(1) communication phases, with high probability for n=Ω(P ^3+ε ) . Received June 1, 1997; revised March 10, 1998.