An optimal parallel algorithm for planar cycle separators

We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log² n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385.     

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.     

A 2n−2 step algorithm for routing in ann ×n array with constant-size queues

In this paper we describe a deterministic algorithm for solving any 1–1 packet-routing problem on ann ×n mesh in 2n–2 steps using constant-size queues. The time bound is optimal in the worst case. The best previous deterministic algorithm for this problem required time 2n+(n/q) using queues of size (q) for any 1qn, and the best previous randomized algorithm required time 2n+(logn) using constant-size queues.This research was supported by the Clear Center at UTD, DARPA Contracts N00014-91-J-1698 and N00014-92-J-1799, Air Force Contract F49620-92-J-0125, Army Contract DAAL-03-86-K-0171, an NSF Presidential Young Investigator Award with matching funds from AT&T and IBM, and by the Texas Advanced Research Program under Grant No. 3972. A preliminary version of this paper appeared in [5].     

Finding a closest visible vertex pair between two polygons

Given nonintersecting simple polygonsP andQ, two verticespP andq Q are said to be visible if does not properly intersectP orQ. We present a parallel algorithm for finding a closest pair among all visible pairs (p,q),pP andqQ. The algorithm runs in time O(logn) using O(n) processors on a CREW PRAM, wheren=¦P¦+¦Q¦. This algorithm can be implemented serially in (n) time, which gives a new optimal sequential solution for this problem.This paper appeared in preliminary form as [1]. This work was supported in part by an AT&T BellLaboratories 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 the author was with the Department of Computer Science at the University of Illinois at Urbana-Champaign.     

Algorithms for computing the center of area of a convex polygon

The center of area of a convex polygonP is the unique pointp ^* that maximizes the minimum area overlap betweenP and any halfplane that includesp ^*. We show thatp ^* is unique and present two algorithms for its computation. The first is a combinatorial algorithm that runs in timeO (n ⁶ log² n). The second is a numerical algorithm that runs in timeO(GK(n+K)) whereK represents the number of desired bits of precision in the output coordinates andG the number of bits used to represent the coordinates of the input polygon vertices. We conclude with a discussion of implementation issues and related results.Research partially supported by the second author's NSF grant CCR-8351468, at Johns Hopkins University and Smith College.     

Parallel algorithms for routing in nonblocking networks

We construct nonblocking networks that are efficient not only as regards their cost and delay, but also as regards the time and space required to control them. In this paper we present the first simultaneous weakly optimal solutions for the explicit construction of nonblocking networks, the design of algorithms and data-structures. Weakly optimal is in the sense that all measures of complexity (size and depth of the network, time for the algorithm, space for the data-structure, and number of processor-time product) are within one or more logarithmic factors of their smallest possible values. In fact, we construct a scheme in which networks withn inputs andn outputs have sizeO(n(logn)²) and depthO(logn), and we present deterministic and randomized on-line parallel algorithms to establish and abolish routes dynamically in these networks. In particular, the deterministic algorithm usesO((logn)⁵) steps to process any number of transactions in parallel (with one processor per transaction), maintaining a data structure that useO(n(logn)²) words.     

Finding all periods and initial palindromes of a string in parallel

An optimalO(log logn)-time CRCW-PRAM algorithm for computing all period lengths of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the length of the string. The algorithm can be used to find all initial palindromes of a string in the same time and processor bounds. Both algorithms are the fastest possible over a general alphabet. We derive a lower bound for finding initial palindromes by modifying a known lower bound for finding the period length of a string [9]. Whenp processors are available the bounds become (n/p+log_1+p/n2p).This work was partially supported by NSF Grant CCR-90-14605. D. Breslauer was partially supported by an IBM Graduate Fellowship while studying at Columbia University and by a European Research Consortium for Informatics and Mathematics postdoctoral fellowship.     

Ray shooting in polygons using geodesic triangulations

LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO( logn) time.Work by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Micha Sharir has been supported by ONR Grants N00014-89-J-3042 and N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Seven fingers allow force-torque closure grasps on any convex polyhedron

We prove that a robot hand whose fingers make frictionless contact with a convex polyhedral object will be able to find a grasp where the hand can exert any desired force-torque on the object provided the hand has seven fingers. We present an algorithm for grasping any convex polyhedron and we prove rigorously that it works for any convex polyhedron. The algorithm requiresO(n ^3/2logn) steps (in the worst case) wheren is the number of vertices.     

A parallel algorithm to construct a dominance graph on nonoverlapping rectangles

A parallel algorithm to generate the dominance graph on a collection of nonoverlapping iso-oriented rectangles is presented. This graph arises from the constraint graph commonly used in compaction algorithms for VLSI circuits. The dominance graph expresses the notion of aboveness on a collection of nonoverlapping rectangles: it is the directed graph which contains an edge from a rectangleb to rectanglec iffc is immediately aboveb. The algorithm is based on the divide and conquer paradigm; in the EREW PRAM model, it has time complexityO(log² n), usingn/logn processors. Its processor-time product isO(nlogn), which is optimal.     

Fast parallel Lyndon factorization with applications

It is shown that the Lyndon decomposition of a word ofn symbols can be computed by ann-processor CRCW PRAM inO(logn) time. Extensions of the basic algorithm convey, within the same time and processors bounds, efficient parallel solutions to problems such as finding the lexicographically minimum or maximum suffix for all prefixes of the input string, and finding the lexicographically least rotation of all prefixes of the input.A. Apostolico's research was supported in part by the French and Italian Ministries of Education, by British Research Council Grant SERC-E76797, by NSF Grants CCR-89-00305 and CCR-9201078, by NIH Library of Medicine Grant R01 LM05118, by AFOSR Grant 89NM682, and by NATO Grant CRG 900293. M. Crochemore's research was supported in part by PRC Mathématiques et Informatique and by NATO Grant CRG 900293.     

Numerical stability of a convex hull algorithm for simple polygons

A numerically stable and optimalO(n)-time implementation of an algorithm for finding the convex hull of a simple polygon is presented. Stability is understood in the sense of a backward error analysis. A concept of the condition number of simple polygons and its impact on the performance of the algorithm is discussed. It is shown that if the condition number does not exceed (1+O())/(3), then, in floating-point arithmetic with the unit roundoff, the algorithm produces the vertices of a convex hull for slightly perturbed input points. The relative perturbation does not exceed 3(1+O()).J. W. Jaromczyk was partially supported by a grant from the Center for Robotics and Manufacturing Systems at the University of Kentucky and G. W. Wasilkowski was partially supported by the National Science Foundation under Grants CCR-89-05371 and CCR-91-14042.     

Undirecteds-t connectivity in polynomial time and sublinear space

Thes-t connectivity problem for undirected graphs is to decide whether two designated vertices,s andt, are in the same connected component. This paper presents the first known deterministic algorithms solving undirecteds-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. Forn vertex,m edge graphs, the simplest of our algorithms uses spaceO(s),n ^1/2log₂ nsnlog₂ n, and timeO(((m+n)n ² log² n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space (nlogn), its time bound isO((m+n)logn), close to the optimal time for the problem. Another generalization uses less space, but more time: spaceO(n ^1/logn), for 2log₂ n, and timen ^O(). For constant the time remains polynomial.     

Dynamic half-space range reporting and its applications

We consider the half-space range-reporting problem: Given a setS ofn points in ^d, preprocess it into a data structure, so that, given a query half-space , allk points ofS can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n m n ^d/2 and an arbitrarily small positive constant , we achieveO(m ¹⁺) space and preprocessing time, O((n/m ^d/2 logn+k) query time, and O(m¹⁺n) amortized update time (d 3). We present, among others, the following applications: an O(n¹⁺)-time algorithm for computing convex layers in ³, and an output sensitive algorithm for computing a level in an arrangements of planes in ³, whose time complexity is O((b+n) n, whereb is the size of the level.Work by the first author has been supported by National Science Foundation Grant CCR-91-06514. A preliminary version of this paper appeared in Agarwalet al. [2], which also contains the results of [20] on dynamic bichromatic closest pair and minimum spanning trees.     

Parallel integer sorting using small operations

We consider the problem of sortingn integers in the range [0,n ^c -1], wherec is a constant. It has been shown by Rajasekaran and Sen [14] that this problem can be solved optimally inO(logn) steps on an EREW PRAM withO(n) n -bit operations, for any constant >O. Though the number of operations is optimal, each operation is very large. In this paper, we show thatn integers in the range [0,n ^c -1] can be sorted inO(logn) time withO(nlogn)O(1)-bit operations andO(n) O(logn)-bit operations. The model used is a non-standard variant of an EREW PRAMtthat permits processors to have word-sizes ofO(1)-bits and (logn)-bits. Clearly, the speed of the proposed algorithm is optimal. Considering that the input to the problem consists ofO (n logn) bits, the proposed algorithm performs an optimal amount of work, measured at the bit level.This work was partially supported by The Northeast Parallel Architectures Center (NPAC) at Syracuse University, Syracuse, NY 13244 and The Rome Air Development Center, under contract F30602-88-D-0027.     

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.     

Parallel algorithms for separation of two sets of points and recognition of digital convex polygons

Given two finite sets of points in a plane, the polygon separation problem is to construct a separating convexk-gon with smallestk. In this paper, we present a parallel algorithm for the polygon separation problem. The algorithm runs inO(logn) time on a CREW PRAM withn processors, wheren is the number of points in the two given sets. The algorithm is cost-optimal, since (n logn) is a lower-bound for the time needed by any sequential algorithm. We apply this algorithm to the problem of finding a convex polygon, with the minimal number of edges, for which a given convex region is its digital image. The algorithm in this paper constructs one such polygon with possibly two more edges than the minimal one.The research is sponsored by NSERC Operating Grant OGPIN 007.     

Using geometry to solve the transportation problem in the plane

LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦=, andn=k+. These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n^2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the ₁ metric, the ₂ metric, and the metric. The running time for the ₁ and metrics can be improved to 0(n²(logn)³ logN).D. S. Atkinson was supported by the National Science Foundation under Grant CCR90-57481PYI. P. M. Vaidya was supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

Fast linear expected-time algorithms for computing maxima and convex hulls

This paper examines the expected complexity of boundary problems on a set ofN points inK-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points usingKN + O (N^1–1/K log^1/K N) expected scalar comparisons, for fixedK 2. A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixedK 2, an algorithm computes the convex hull of the set in 2KN + O(N^1–1/K log^1/KN) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.This work was performed while this author was visiting AT&T Bell Laboratories.