Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

A sublogarithmic convex hull algorithm

We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs inO(logn/log logn) time usingO(n log logn/logn) processors in theCommon crcw pram computational model, which is shown to be time and cost optimal. The algorithm is based onn ^1/3 divide-and-conquer and uses a simple pointer-based data structure.Part of this work was done when the last three authors were at the Department of Computer and Information Science, Linköping University. The research of the second author was supported by the Academy of Finland.     

An optimal convex hull algorithm in any fixed dimension

We present a deterministic algorithm for computing the convex hull ofn points inE ^d in optimalO(n logn+n ^⌞d/2⌟ ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram ofn points ind-space in optimalO(n logn+n ^⌜d/2⌝ ) time. This research was supported in part by the National Science Foundation under Grant CCR-9002352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. A preliminary version of this paper has appeared in “An optimal convex hull algorithm and new results on cuttings”,Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science, October 1991, pp. 29–38. The convex hull algorithm given in the present paper, although similar in spirit, is considerably simpler than the one given in the proceedings.     

Incremental and Decremental Maintenance of Planar Width

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^ε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^ε).     

Computing minimum-area rectilinear convex hull and L-shape

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n²) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.     

Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E ⁴ . Our algorithm runs in time and uses O(n+f) space. This is the first algorithm within a polylogarithmic factor of optimal time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E ³ and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the ``ultimate convex hull algorithm' of Kirkpatrick and Seidel in E ² and also leads to improved output-sensitive results on constructing convex hulls in E ^d for any even constant d > 4. Received August 3, 1995, and in revised form September 19, 1996.     

A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the enumeration of the vertices of an arrangement or of a convex polyhedron, in arbitrary dimension. The algorithm has the following properties:

Optimal output-sensitive convex hull algorithms in two and three dimensions

We present simple output-sensitive algorithms that construct the convex hull of a set ofn points in two or three dimensions in worst-case optimalO (n logh) time andO (n) space, whereh denotes the number of vertices of the convex hull. This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

Voronoi Diagrams and Convex Hulls of Random Moving Points

This report considers the expected combinatorial complexity of the Euclidean Voronoi diagram and the convex hull of sets of n independent random points moving in unit time between two positions drawn independently from the same distribution in R ^d for fixed d\ge 2 as n→∈fty . It is proved that, when the source and destination distributions are the uniform distribution on the unit d -ball, these complexities are Θ(n ^(d+1)/d ) for the Voronoi diagram and O(n ^(d-1)/(d+1) log n) for the convex hull. Additional results for the convex hull are O( log ^d n) for the uniform distribution in the unit d -cube and O( log ^(d+1)/2 n) for the d -dimensional normal distribution. Received November 23, 1998, and in revised form July 8, 1999.     

Polygonizations of point sets in the plane

We examine the different ways a set ofn points in the plane can be connected to form a simple polygon. Such a connection is called apolygonization of the points. For some point sets the number of polygonizations is exponential in the number of points. For this reason we restrict our attention to star-shaped polygons whose kernels have nonempty interiors; these are callednondegenerate star-shaped polygons.We develop an algorithm and data structure for determining the nondegenerate star-shaped polygonizations of a set ofn points in the plane. We do this by first constructing an arrangement of line segments from the point set. The regions in the arrangement correspond to the kernels of the nondegenerate star-shaped polygons whose vertices are the originaln points. To obtain the data structure representing this arrangement, we show how to modify data structures for arrangements of lines in the plane. This data structure can be computed inO(n ⁴) time and space. By visiting the regions in this data structure in a carefully chosen order, we can compute the polygon associated with each region inO(n) time, yielding a total computation time ofO(n ⁵) to compute a complete list ofO(n ⁴) nondegenerate star-shaped polygonizations of the set ofn points.     

Off-Line Maintenance of Planar Configurations

We achieve anO(log n) amortized time bound per operation for the off-line version of the dynamic convex hull problem in the plane. In this problem, a sequence ofninsert,delete, andqueryinstructions are to be processed, where each insert instruction adds a new point to the set, each delete instruction removes an existing point, and each query requests a standard convex hull search. We process the entire sequence in totalO(n log n) time andO(n) space. Alternatively, we can preprocess a sequence ofninsertions and deletions inO(n log n) time and space, then answer queries in history inO(log n) time apiece (a query in history means a query comes with a time parametert, and it must be answered with respect to the convex hull present at timet). The same bounds also hold for the off-line maintenance of several related structures, such as the maximal vectors, the intersection of half-planes, and the kernel of a polygon. Achieving anO(log n) per-operation time bound for theon-lineversions of these problems is a longstanding open problem in computational geometry.     

Cutting a Convex Polyhedron Out of a Sphere

Given a convex polyhedron P of n vertices inside a sphere Q, we give an O(n ³)-time algorithm that cuts P out of Q by using guillotine cuts and has cutting cost O(log² n) times the optimal.     

Computing optimal islands

Let S be a bicolored set of n points in the plane. A subset I of S is an island if there is a convex set C such that I=C∩S. We give an O(n³)-time algorithm to compute a monochromatic island of maximum cardinality. Our approach is adapted to optimize similar (decomposable) objective functions. Finally, we use our algorithm to give an O(logn)-approximation for the problem of computing the minimum number of convex polygons that cover a class region.     

A new duality result concerning voronoi diagrams

A new duality between order-k Voronoi diagrams inE ^d and convex hulls inE ^d+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram forn points in the plane inO(k ² n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung.     

Minimization of convex functions on the convex hull of a point set

A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in R ⁿ is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in R ^m , which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.     

Finding the convex hull of a simple polygon

It is well known that the convex hull of a set of n points in the plane can be found by an algorithm having worst-case complexity O(n log n). A short linear-time algorithm for finding the convex hull when the points form the (ordered) vertices of a simple (i.e., non-self-intersecting) polygon is given.     

The order of points on the second convex hull of a simple polygon

Given a setV of points on the plane, if {q ₁,...,q _n } is the set of points on the second convex hull ofV, the order in which these points are visited in anyV-gon is characterized. This order must verify two similar conditions to those of Kuratowski's theorem for planar graphs. Moreover, the number of possible orders that verify these conditions is obtained. It isO(5 ⁿ ).