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]

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]

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]