Randomized incremental construction of simple abstract Voronoi diagrams in 3-space

We introduce the simple abstract Voronoi diagram in 3-space as an abstraction of the usual Voronoi diagram. We show that the 3-dimensional simple abstract Voronoi diagram of n sites can be computed in O(n²) expected time using O(n²) expected space by a randomized algorithm. The algorithm is based on the randomized incremental construction technique of Clarkson and Shor (1989). We apply the algorithm to some concrete types of such diagrams: power diagrams, diagrams under ellipsoid convex distance functions, and diagrams under the Hausdorff distance for sites that are parallel segments all having the same length.     

The greedy triangulation can be computed from the Delaunay triangulation in linear time

The greedy triangulation of a finite planar point set is obtained by repeatedly inserting a shortest diagonal that does not cross those already in the plane. The Delaunay triangulation, which is the straight-line dual of the Voronoi diagram, can be produced in O(nlogn) worst-case time, and often even faster, by several practical algorithms. In this paper we show that for any planar point set S, if the Delaunay triangulation of S is given, then the greedy triangulation of S can be computed in linear worst-case time (and linear space).     

How many maxima can there be?

Let C be a planar region. Choose n points p₁,,p_nI.I.D. from the uniform distribution over C. Let M^C_n be the number of these points that are maximal. If C is convex it is known that either E(M^C_n)=Θ(√n)> or E(M^C_n)=O(log n). In this paper we will show that, for general C, there is very little that can be said, a-priori, about E(M^C_n). More specifically we will show that if g is a member of a large class of functions then there is always a region C such that E(M^C_n)=Θ(g(n)). This class contains, for example, all monotically increasing functions of the form g(n)= nln^βn, where 0<<1 and β0. This class also contains nondecreasing functions like g(n)=ln^*n. The results in this paper remain valid in higher dimensions.     

Higher-dimensional voronoi diagrams in linear expected time

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ∵(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ∵(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense. Based upon work supported by the National Science Foundation under Grant No. CCR-8658139 while the author was a student at Carnegie-Mellon University.     

Circular permutation graph family with applications

In a circular permutation diagram, there are two sets of terminals on two concentric circles: C_in and C_out. Given a permutation Π = [π₁, π₂, …, π_n], terminal i on C_in and terminal π_i on C_out are connected by a wire. The intersection graph G_c of a circular permutation diagram D_c is called a circular permutation graph of a permutation Π corresponding to the diagram D_c. The set of all circular permutation graphs of a permutation Π is called the circular permutation graph family of permutation Π. In this paper, we propose the following: (1) an O(V + E) time algorithm to check if a labeled graph G = (V, E) is a labeled circular permutation graph. (2) An O(n log n + nt) time algorithm to find a maximum independent set of a family, where n = Π and t is the cardinality of the output. (Number t in the worst case is O(n). However, if Π is uniformly distributed (and independent from i), its expected value is O(√n).) (3) An O(min(δV_clog logV_c,V_clogV_c) + E_c) time algorithm for finding a maximum independent set of a circular permutation diagram D_c, where δ is the minimum degree of vertices in the intersection graph G_c = (V_c,E_c) of D_c. (4) An O(n log log n) time algorithm for finding a maximum clique and the chromatic number of a circular permutation diagram, where n is the number of wires in the diagram.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Consequences of an algorithm for bridged graphs

Chepoi showed that every breadth first search of a bridged graph produces a cop-win ordering of the graph. We note here that Chepoi's proof gives a simple proof of the theorem that G is bridged if and only if G is cop-win and has no induced cycle of length four or five, and that this characterization together with Chepoi's proof reduces the time complexity of bridged graph recognition. Specifically, we show that bridged graph recognition is equivalent to (C₄,C₅)-free graph recognition, and reduce the best known time complexity from O(n⁴) to O(n^3.376).     

Minimal enclosing parallelepiped in 3D

We investigate the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. We give two mathematical properties of these parallelepipeds, from which we derive two algorithms of theoretical complexity O(n⁶). Experiments show that in practice our quickest algorithm runs in O(n²) (at least for n10⁵). We also present our application in structural biology.     

Cartographic line simplification and polygon CSG formulæ in O(n log n) time

A constructive solid geometry (CSG) conversion for a polygon takes a list of vertices and produces a formula representing the polygon as an intersection and union of primitive halfspaces. The cartographers' favorite line simplification algorithm recursively selects from a list of data points those to be used to represent a linear feature, such as a coastline, on a map. By using a data structure that maintains convex hulls of polygonal lines under splits, both were known to have O(n log n) time solutions in the worst-case. This paper shows that both are easier than sorting by presenting an O(n log^* n) algorithm for maintaining convex hulls under splits at extreme points. It opens the question of whether there are practical, linear-time solutions to these problems.     

Graphs with prescribed local connectivities

A graph G is locally n-connected (locally n-edge connected) if the neighborhood of each vertex of G is n-connected (n-edge connected). The local connectivity (local edge-connectivity) of G is the maximum n for which G is locally n-connected (locally n-edge connected). It is shown that if k and m are integers with O k < m, then a graph exists which has connectivity m and local connectivity k. Furthermore, such a graph with smallest order is determined. Corresponding results are obtained involving the local connectivity and the local edge-conectivity.     

On fat partitioning, fat covering and the union size of polygons

The complexity of the contour of the union of simple polygons with n vertices in total can be O(n²) in general. A notion of fatness for simple polygons is introduced that extends most of the existing fatness definitions. It is proved that a set of fat polygons with n vertices in total has union complexity O(n log log n), which is a generalization of a similar result for fat triangles (Matou ek et al., 1994). Applications to several basic problems in computational geometry are given, such as efficient hidden surface removal, motion planning, injection molding, and more. The result is based on a new method to partition a fat simple polygon P with n vertices into O(n) fat convex quadrilaterals, and a method to cover (but not partition) a fat convex quadrilateral with O(l) fat triangles. The maximum overlap of the triangles at any point is two, which is optimal for any exact cover of a fat simple polygon by a linear number of fat triangles.     

Manifolds of idemopotent matrices

Let M_n be the set of n×n matrices and r a nonnegative integer with r ≤ n. It is known,from Lie groups, that the rank r idempotent matrices in M_n form an arcwise connected 2n (n-r)-dimensional analytic manifold. This paper provides an elementary proof of this result making it accessible to a larger audience.     

Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.

The minimum weight triangulation problem with few inner points

We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem can be solved in O(n³) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6^kn⁵logn) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k=O(logn). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k inner points.     

Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model

In this paper, we present a direct approach for routing a shortest rectilinear path between two points among a set of rectilinear obstacles in a two-layer interconnection model that is used for VLSI routing applications. The previously best known direct approach for this problem takes O(nlog²n) time and O(nlogn) space, where n is the total number of obstacle edges. By using integer data structures and an implicit graph representation scheme (i.e., a generalization of the distance table method), we improve the time bound to O(nlog^3/2n) while still maintaining the O(nlogn) space bound. Comparing with the indirect approach for this problem, our algorithm is simpler to implement and is probably faster for a quite large range of input sizes.     

Lower bounds for computing geometric spanners and approximate shortest paths

We consider the problems of constructing geometric spanners, possibly containing Steiner points, for a set of n input points in d-dimensional space , and constructing spanners and approximate shortest paths among a collection of polygonal obstacles on the plane. The complexities of these problems are shown to be Ω(n log n) in the algebraic computation tree model. Since O(n log n)-time algorithms are known for solving these problems, our lower bounds are tight up to a constant factor.     

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree

Given an edge-weighted tree T and an integer p1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2−2/(p+1))-approximation algorithm which runs in O(p^p−1n^p−1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p−1)!·n) time.