On the ultimate convex hull algorithm in practice

Kirkpatrick and Seidel [13,14] recently proposed an algorithm for computing the convex hull of n points in the plane that runs in O(n log h) worst case time, where h denotes the number of points on the convex hull of the set. Here a modification of their algorithm is proposed that is believed to run in O(n) expected time for many reasonable distributions of points. The above O(n log h) algorithmsare experimentally compared to the O(n log n) ‘throw-away’ algorithms of Akl, Devroye and Toussaint [2, 8, 20]. The results suggest that although the O(n Log h) algorithms may be the ‘ultimate’ ones in theory, they are of little practical value from the point of view of running time.     

Finding the intersection of n half-spaces in time O(nlogn)

Given a set of n half-spaces in three dimensional space, we develop an algorithm for finding their common intersection in time O(n log n). The intersection, if nonempty, is presented as a convex polyhedron. The algorithm is summarized as follows: (i) the half-spaces are placed in two sets depending upon whether they contain or do not contain the origin; (ii) the half-spaces in each of these sets are dualized to points, and the convex hulls of the dualized sets are obtained in time O(n log n); (iii) since the half-space intersection is nonempty if and only if these two convex hulls are disjoint, a separating plane is found, also in time O(n log n); (iv) after applying a linear spatial transformation which maps the separating plane to infinity, the convex hull of the union of the two transformed convex hulls is the transformed intersection of the half-spaces. Since the letter can be found in time O(n), the overall running time of the procedure is O(n log n). A significant consequence of this result is that a three-variable linear, or convex, programming problem can be asymptotically solved faster than by the Simplex algorithm, in the worst case.     

Capturing crossings: Convex hulls of segment and plane intersections

We give a simple O(nlogn) algorithm to compute the convex hull of the (possibly Θ(n²)) intersection points in an arrangement of n line segments in the plane. We also show an arrangement of dn hyperplanes in d-dimensions whose arrangement has Θ(nd−1) intersection points on the convex hull.     

On the application of the convex hull to histogram analysis in threshold selection

A recently proposed algorithm for computing the convex hull of a grey-level histogram in image segmentation is shown to be inefficient due to the fact that it does not exploit the histogram's structure. It is pointed out that a histogram is a weakly externally visible polygon and thus a very simple linear convex hull algorithm will work for such applications.     

Optimal algorithms for computing the minimum distance between two finite planar sets

It is shown in this paper that the minimum distance between two finite planar sets of n points can be computer in O(n log n) worst-case running time and that this is optimal to within a constant factor. Furthermore, when the sets form a convex polygon this complexity can be reduced O(n).     

Efficient parallel solutions to some geometric problems

This paper presents new algorithms for solving some geometric problems on a shared memory parallel computer, where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location. The algorithms are quite different from known sequential algorithms, and are based on the use of a new parallel divide-and-conquer technique. One of our results is an O(log n) time, O(n) processor algorithm for the convex hull problem. Another result is an O(log n log log n) time, O(n) processor algorithm for the problem of selecting a closest pair of points among n input points.     

A Fast Parallel Algorithm for Convex Hull Problem of Multi-Leveled Images

In this paper, we propose a parallel algorithm to solve the convex hull problem for an (n×n) multi-leveled image using a reconfigurable mesh connected computer of the same size as a computational model. The algorithm determines parallely the convex hull of all the connected components of the multileveled image. It is based on some geometric properties and a top-down strategy. The complexity of the algorithm is O(logn) times. Using some approximations on the component contours, this complexity is reduced to O(logm) times where m is the number of the vertices of the convex hull of the biggest component of the image.This complexity is reached thanks to the polymorphic properties of the mesh where all the components are simultaneously and separately processed.     

Constructing strongly convex hulls using exact or rounded arithmetic

One useful generalization of the convex hull of a setS ofn points is the ?-strongly convex δ-hull. It is defined to be a convex polygon with vertices taken fromS such that no point inS lies farther than δ outside and such that even if the vertices of are perturbed by as much as ?, remains convex. It was an open question as to whether an ?-strongly convexO(?)-hull existed for all positive ?. We give here anO(n logn) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an ?-strongly convexO(? + μ)-hull inO(n logn) time using rounded arithmetic with rounding unit μ. This is the first rounded-arithmetic convex-hull algorithm which guarantees a convex output and which has error independent ofn.     

Applications of a two-dimensional hidden-line algorithm to other geometric problems

Recently ElGindy and Avis (EA) presented anO(n) algorithm for solving the two-dimensional hidden-line problem in ann-sided simple polygon. In this paper we show that their algorithm can be used to solve other geometric problems. In particular, triangulating anL-convex polygon and finding the convex hull of a simple polygon can be accomplished inO(n) time, whereas testing a simple polygon forL-convexity can be done inO(n ²) time.     

Design and Implementation of a Practical Parallel Delaunay Algorithm

This paper describes the design and implementation of a practical parallel algorithm for Delaunay triangulation that works well on general distributions. Although there have been many theoretical parallel algorithms for the problem, and some implementations based on bucketing that work well for uniform distributions, there has been little work on implementations for general distributions. We use the well known reduction of 2D Delaunay triangulation to find the 3D convex hull of points on a paraboloid. Based on this reduction we developed a variant of the Edelsbrunner and Shi 3D convex hull algorithm, specialized for the case when the point set lies on a paraboloid. This simplification reduces the work required by the algorithm (number of operations) from O(n log ² n) to O(n log n) . The depth (parallel time) is O( log ³ n) on a CREW PRAM. The algorithm is simpler than previous O(n log n) work parallel algorithms leading to smaller constants. Initial experiments using a variety of distributions showed that our parallel algorithm was within a factor of 2 in work from the best sequential algorithm. Based on these promising results, the algorithm was implemented using C and an MPI-based toolkit. Compared with previous work, the resulting implementation achieves significantly better speedups over good sequential code, does not assume a uniform distribution of points, and is widely portable due to its use of MPI as a communication mechanism. Results are presented for the IBM SP2, Cray T3D, SGI Power Challenge, and DEC AlphaCluster. Received June 1, 1997; revised March 10, 1998.     

Minimum polygonal separation

In this paper we study the problem of polygonal separation in the plane, i.e., finding a convex polygon with minimum number k of sides separating two given finite point sets (k-separator), if it exists. We show that for k = Θ(n), Ω(n log n) is a lower bound to the running time of any algorithm for this problem, and exhibit two algorithms of distinctly different flavors. The first relies on an O(n log n)-time preprocessing task, which constructs the convex hull of the internal set and a nested star-shaped polygon determined by the external set; the k-separator is contained in the annulus between the boundaries of these two polygons and is constructed in additional linear time. The second algorithm adapts the prune-and-search approach, and constructs, in each iteration, one side of the separator; its running time is O(kn), but the separator may have one more side than the minimum.     

A time-optimal parallel algorithm for three-dimensional convex hulls

In this paper we present an O(1/ logn)-time parallel algorithm for computing the convex hull ofn points in ³. This algorithm usesO(@#@ n^1+a) processors on a CREW PRAM, for any constant 0 < 1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log² n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(logn)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.This paper was presented in preliminary form at the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, May 1993 [32]. The work of N. M. Amato was supported in part by an AT&T Bell Laboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while N. M. Amato was with the Department of Computer Science at the University of Illinois. The work of F. P. Preparata was supported in part by NSF Grants CCR-91-96152, CCR-91-96176, and ONR Contract N00014-91-J-4052, ARPA order 8225.     

An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon

The convex differences tree (CDT) representation of a simple polygon is useful in computer graphics, computer vision, computer aided design and robotics. The root of the tree contains the convex hull of the polygon and there is a child node recursively representing every connectivity component of the set difference between the convex hull and the polygon. We give an O(n log K + K log² n) time algorithm for constructing the CDT, where n is the number of polygon vertices and K is the number of nodes in the CDT. The algorithm is adaptive to a complexity measure defined on its output while still being worst case efficient. For simply shaped polygons, where K is a constant, the algorithm is linear. In the worst case K = O(n) and the complexity is O(n log² n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure.     

Aligning Two Convex Figures to Minimize Area or?Perimeter

Given two compact convex sets P and Q in the plane, we consider the problem of finding a placement ? P of P that minimizes the convex hull of ? P∪Q. We study eight versions of the problem: we consider minimizing either the area or the perimeter of the convex hull; we either allow ? P and Q to intersect or we restrict their interiors to remain disjoint; and we either allow reorienting P or require its orientation to be fixed. In the case without reorientations, we achieve exact near-linear time algorithms for all versions of the problem. In the case with reorientations, we compute a (1+ε)-approximation in time?O(ε ^?1/2log?n+ε ^?3/2log? ^a (1/ε)) if the two sets are convex polygons with n vertices in total, where a∈{0,1,2} depending on the version of the problem.     

External watchman routes

We consider the problem of finding a shortest watchman route from which the exterior of a polygon is visible (external watchman route). We present an O (n ⁴ log logn) algorithm to find shortest external watchman routes for simple polygons by transforming the external watchman route problem to a set of internal watchman route problems. Also, we present faster external watchman route algorithms for special cases. These include optimal O (n) algorithms for convex, monotone, star and spiral polygons and an O (n log logn) algorithm for rectilinear polygons.This work was supported in part by a grant from Texas Instruments, Inc. to S. Ntafos     

An optimal scheduling algorithm for preemptable real-time tasks

An optimal scheduling algorithm is presented for real-time tasks with arbitrary ready times and deadlines in single processor systems. The time complexity of the algorithm is O(n log n), which improves the best previous result of O(n²). Furthermore, the lower bound of the worst-case time complexity of the problem is shown to be of O(n log n) and therefore the time complexity of the presented algorithm is shown to be lower bound.     

A parallel median algorithm

We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)²) parallel time on O(n) processors in Valiant's comparison model.     

An O((log log n)2) time algorithm to compute the convexhull of sorted points on reconfigurable meshes

The problem of computing the convex hull of a set of n sorted points in the plane is one of the fundamental tasks in image processing, pattern recognition, cellular network design, and robotics, among many others. Somewhat surprisingly, in spite of a great deal of effort, the best previously known algorithm to solve this problem on a reconfigurable mesh of size √n×√n was running in O(log2 n) time. It was open for more than ten years to obtain an algorithm for this important problem running in sublogarithmic time. Our main contribution is to provide the first breakthrough: we propose an almost optimal convex hull algorithm running in O((log log n)²) time on a reconfigurable mesh of size √n×√n. With slight modifications, this algorithm can be implemented to run in O((log log n)²) time on a reconfigurable mesh of size √n/loglogn×√n/loglogn. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take Ω(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.     

On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.