Computing convexity properties of images on a pyramid computer

We present efficient parallel algorithms for using a pyramid computer to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base ofn simple processing elements arranged in ann ^1/2 ×n ^1/2 square, the running times of the algorithms range from Θ(logn) to find the extreme points of a convex figure in a digitized picture, to Θ(n ^1/6) to find the diameter of a labeled figure, Θ(n ^1/4 logn) to find the extreme points of every figure in a digitized picture, to Θ(n ^1/2) to find the extreme points of every labeled set of processing elements. Our results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. We also show the sensitivity of efficient pyramid-computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture.     

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.     

A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces

This paper presents a new and simple scheme to describe the convex hull in R^d,which only uses three kinds of the faces of the convex hull.i.e.,the d-1-faces,d-2-faces and 0-faces.Thus,we develop and efficient new algorithm for constructing the convex hull of a finite set of points incrementally.This algorithm employs much less storage and time than that of the previously-existing approaches.The analysis of the runniing time as well as the storage for the new algorithm is also theoretically made.The algorithm is optimal in the worst case for even d.     

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.     

Finding the intersection of two convex polyhedra

Given two convex polyhedra in three-dimensional space, we develop an algorithm to (i) test whether their intersection is empty, and (ii) if so to find a separating plane, while (iii) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in timeO (nlogn), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (iii) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point.     

A note on linear expected time algorithms for finding convex hulls

Considern independent identically distributed random vectors fromR ^d with common densityf, and letE (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfyE (C)=0(n) for certain classes of densities. In this note, we show thatE (C)=0(n) for algorithms that use a “throw-away” pre-processing step whenf is bounded away from 0 and ∞ on any nondegenerate rectangle ofR ².     

On counting pairs of intersecting segments and off-line triangle range searching

We describe a method for decomposing planar sets of segments and points. Using this method we obtain new efficientdeterministic algorithms for counting pairs of intersecting segments, and for answering off-line triangle range queries. In particular we obtain the following results:

1. Givenn segments in the plane, the number of pairs of intersecting segments is counted in timeO(n ^1+?+K ^1/3 n ^2/3+?), whereK is the number of intersection points among the segments, and ?>0 is an arbitrarily small constant.
2. Givenn segments in the plane which are colored with two colors, the number of pairs ofbichromatic intersecting segments is counted in timeO(n ^1+?+K _m ^1/3 n ^2/3+?), whereK _m is the number ofmonochromatic intersection points, and ?>0 is an arbitrarily small constant.
3. Givenn weighted points andn triangles on a plane, the sum of weights of points in each triangle is computed in timeO(n ^1+ε+?^1/3 n ^2/3+ε), where ? is the number of vertices in the arrangement of the triangles, and ?>0 is an arbitrarily small constant.

The above bounds depend sublinearly on the number of intersections among input segmentsK (resp.K _m , ?), which is desirable sinceK (resp.K _m , ?) can range from zero toO(n ²). All of the above algorithms use optimal Θ(n) storage. The constants of proportionality in the big-Oh notation increase as ? decreases. These results are based on properties of the sparse nets introduced by Chazelle [Cha3].     

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.     

Optimal algorithms for some intersection radius problems

The intersection radius of a set ofn geometrical objects in ad-dimensional Euclidean space,E ^d , is the radius of the smallest closed hypersphere that intersects all the objects of the set. In this paper, we describe optimal algorithms for some intersection radius problems. We first present a linear-time algorithm to determine the smallest closed hypersphere that intersects a set of hyperplanes inE ^d , assumingd to be a fixed parameter. This is done by reducing the problem to a linear programming problem in a (d+1)-dimensional space, involving 2n linear constraints. We also show how the prune-and-search technique, coupled with the strategy of replacing a ray by a point or a line can be used to solve, in linear time, the intersection radius problem for a set ofn line segments in the plane. Currently, no algorithms are known that solve these intersection radius problems within the same time bounds.     

A note on point location in arrangements of hyperplanes

We give an algorithm for point location in an arrangement of n hyperplanes in E^d with running time poly(d,logn) and space O(n^d). The space improves on the O(n^d+ε) bound of Meiser's algorithm [Inform. and Control 106 (1993) 286] that has a similar running time.     

Multisearch Techniques: Parallel Data Structures on Mesh-Connected Computers

The multisearch problem is defined as follows. Given a data structure D modeled as a graph with n constant-degree nodes, perform O(n) searches on D. Let r be the length of the longest search path associated with a search process, and assume that the paths are determined "on-line." That is, the search paths may overlap arbitrarily. In this paper, we solve the multisearch problem for certain classes of graphs in O([formula] + r ([formula]/log n)) time on a [formula] × [formula]n mesh-connected computer. For many data structures, the search path traversed when answering one search query has length r = O(log n). For these cases, our algorithm processes O(n) such queries in asymptotically optimal Θ([formula]) time. The classes of graphs we consider contain many of the important data structures that arise in practice, ranging from simple trees to Kirkpatrick hierarchical search DAGs. Multisearch is a useful abstraction that can be used to implement parallel versions of standard sequential data structures on a mesh. As example applications, we consider a variety of parallel on-line tree traversals, as well as hierarchical representations of polyhedra and its myriad of applications (line-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).     

Lower bounds for maximal and convex layers problems

In this paper we derive tight lower bounds for the maximal and convex layers problems in the plane. Our lower bound proofs for the maxima problem and convex hull problem are simpler than those previously known. We also obtain an Ω(nlog n) lower bound for the maximal depth problem, and the convex depth problem, when the points are given in sorted order of their x-coordinates.     

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.Research supported in part by NSF Grant MIP-85 21356, ARO Contract DAA G29-85-C0018 under Cornell MSI, and ONR Contract N00014-88-K-0402. This paper is an updated version of a part of [6].     

The complexity of incremental convex hull algorithms in Rd

The complexity of any incremental convex hull algorithm in R^d is shown to be $\text{Ω(n}{}^{\mathrm{<mtext>[</mtext><mtext>(d+1)</mtext><mtext>2</mtext><mtext>]</mtext>}}\text{)}$ for n points and constant d.     

A bidirectional shortest-path algorithm with good average-case behavior

The two-terminal shortest-path problem asks for the shortest directed path from a specified nodes to a specified noded in a complete directed graphG onn nodes, where each edge has a nonnegative length. We show that if the length of each edge is chosen independently from the exponential distribution, and adjacency lists at each node are sorted by length, then a priority-queue implementation of Dijkstra's unidirectional search algorithm has the expected running time Θ(n logn). We present a bidirectional search algorithm that has expected running time Θ(√n logn). These results are generalized to apply to a wide class of edge-length distributions, and to sparse graphs. If adjacency lists are not sorted, bidirectional search has the expected running time Θ(a√n) on graphs of average degreea, as compared with Θ(an) for unidirectional search.     

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.     

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.     

Ready, Set, Go! The Voronoi diagram of moving points that start from a line

It is an outstanding open problem of computational geometry to prove a near-quadratic upper bound on the number of combinatorial changes in the Voronoi diagram of points moving at a common constant speed along linear trajectories in the plane. In this note we observe that this quantity is Θ(n²) if the points start their movement from a common line.     

Finding the convex hull of a sorted point set in parallel

We present a parallel algorithm for finding the convex hull of a sorted planar point set. Our algorithm runs in O(log n) time using O(n/log n) processors in the CREW PRAM computational model, which is optimal. One of the techniques we use to achieve these optimal bounds is the use of a parallel data structure which we call the hull tree.