Search

The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Ω (n + m log m) , and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O ((n + m) log (n + m)) and O (n + m log m log 2 n) time, which are optimal for m = Ω (n) and m = O (n log 3 n) , respectively. In this paper, we give a construction algorithm with O (n + m (log m + log 2 n)) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O (log n) time, then the construction time will become the optimal O (n + m log m) . In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O (log n) time. [ABSTRACT FROM AUTHOR]

Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O (k (n - k) log 2 n + n log 3 n) steps, where O (k (n - k)) is the number of faces in the worst case. This result applies to disjoint line segments in the L p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, a running time with a polylog factor to the number of faces was only achieved for point sites in the L 1 or Euclidean metric before. [ABSTRACT FROM AUTHOR]

We study the diameter of a spanning tree, i.e., the length of its longest simple path, under the imprecise points model, in which each point is assigned its own occurrence region instead of an exact location. We prove that the minimum diameter of a spanning tree of n points each of which is selected from its respective disk (or axis-parallel square) is polynomial-time computable, contrasting with the fact that minimizing the cost of a spanning tree, i.e. the sum of its edge lengths, for imprecise points is known to be NP-hard. This difference is very interesting since for exact points minimizing the cost seems faster than minimizing the diameter [O(nlogn) versus almost cubic running time]. As the first work regarding the minimum diameter of a spanning tree for imprecise points, our main objective is to investigate essential properties that distinguish the problem from NP-hard instead of minimizing the running time [O(n9) for general disks or O(n6) for unit ones]. Our algorithm mainly utilizes farthest-site Voronoi diagrams for disks and axis-parallel squares, and these diagrams would have their own merits. [ABSTRACT FROM AUTHOR]

We present the first algorithm for constructing abstract Voronoi diagrams from bisectors that are unbounded or closed Jordan curves. It runs in expected many steps and space, where is the number of sites, denotes the average number of faces (connected components) per Voronoi region in any diagram of a subset of sites, and is the maximum number of intersection points between any two related bisectors. [ABSTRACT FROM AUTHOR]

Given a set of n sites in the plane, their order-k Voronoi diagram partitions the plane into regions such that all points within one region have the same k nearest sites. The order-k abstract Voronoi diagram offers a unifying framework that represents a wide range of concrete order- k Voronoi diagrams. It is defined in terms of bisecting curves satisfying some simple combinatorial properties, rather than the geometric notions of sites and distance. In this paper we develop a randomized divide-and-conquer algorithm to compute the order- k abstract Voronoi diagram in expected O ( k n 1 + ε ) operations. For solving small sub-instances in the divide-and-conquer process, we also give two auxiliary algorithms with expected O ( k 2 n log ⁡ n ) and O ( n 2 2 α ( n ) log ⁡ n ) time, respectively, where α ( ⋅ ) is the inverse of the Ackermann function. Our approach directly implies an O ( k n 1 + ε ) -time algorithm for several concrete order- k instances such as points in any convex distance, disjoint line segments or convex polygons of constant size in the L p norms, and others. It also provides basic techniques that can enable the application of well-known random sampling techniques to the construction of Voronoi diagrams in the abstract setting and for non-point sites. [ABSTRACT FROM AUTHOR]

We revisit the k-nearest-neighbor ( k-NN) Voronoi diagram and present a new paradigm for its construction. We introduce the k-NN Delaunay graph, which is the graph-theoretic dual of the k-NN Voronoi diagram, and use it as a base to directly compute this diagram in R. We implemented our paradigm in the L and L metrics, using segment-dragging queries, resulting in the first output-sensitive, O(( n+ m)log n)-time algorithm to compute the k-NN Voronoi diagram of n points in the plane, where m is the structural complexity (size) of this diagram. We also show that the structural complexity of the k-NN Voronoi diagram in the L (equiv. L) metric is O(min{ k( n− k),( n− k)}). Efficient implementation of our paradigm in the L (resp. L, 1< p<∞) metric remains an open problem. [ABSTRACT FROM AUTHOR]

Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. [1] we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V ( S ) is a tree, and for each subset S ′ ⊂ S , a forest with one face per site. If the order of Voronoi regions of V ( S ) along the boundary of D is given, then V ( S ) inside D can be constructed in linear time. [ABSTRACT FROM AUTHOR]

Abstract Voronoi diagrams (AVDs) are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and circles. They serve as a unifying concept. Once the bisector system of any concrete type of Voronoi diagram is shown to fulfill the AVD properties, structural results and efficient algorithms become available without further effort. In a concrete order- k Voronoi diagram, all points are placed into the same region that have the same k nearest neighbors among the given sites. This paper is the first to study abstract Voronoi diagrams of arbitrary order k . We prove that their complexity in the plane is upper bounded by 2 k ( n − k ) . So far, an O ( k ( n − k ) ) bound has been shown only for point sites in the Euclidean and L p planes, and, recently, for line segments, in the L p metric. These proofs made extensive use of the geometry of the sites. Our result on AVDs implies a 2 k ( n − k ) upper bound for a wide range of cases for which only trivial upper complexity bounds were previously known, and a slightly sharper bound for the known cases. Also, our proof shows that the reasons for this bound are combinatorial properties of certain permutation sequences. [ABSTRACT FROM AUTHOR]