Parallel algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

A new scheme for the deterministic simulation of PRAMs in VLSI

A deterministic scheme for the simulation of (n, m)-PRAM computation is devised. Each PRAM step is simulated on a bounded degree network consisting of a mesh-of-trees (MT) of siden. The memory is subdivided inn modules, each local to a PRAM processor. The roots of the MT contain these processors and the memory modules, while the otherO(n ²) nodes have the mere capabilities of packet switchers and one-bit comparators. The simulation algorithm makes a crucial use of pipelining on the MT, and attains a time complexity ofO(log² n/log logn). The best previous time bound wasO(log² n) on a different interconnection network withn processors. While the previous simulation schemes use an intermediate MPC model, which is in turn simulated on a bounded degree network, our method performs the simulation directly with a simple algorithm.This work has been supported in part by Ministero della Pubblica Istruzione of Italy under a research grant.     

Fast integer merging on the EREW PRAM

We investigate the complexity of merging sequences of small integers on the EREW PRAM. Our most surprising result is that two sorted sequences ofn bits each can be merged inO(log logn) time. More generally, we describe an algorithm to merge two sorted sequences ofn integers drawn from the set {0, ...,m?1} inO(log logn+log min{n, m}) time with an optimal time-processor product. No sublogarithmic-time merging algorithm for this model of computation was previously known. On the other hand, we show a lower bound of Ω(log min{n, m}) on the time needed to merge two sorted sequences of lengthn each with elements drawn from the set {0, ...,m?1}, implying that our merging algorithm is as fast as possible form=(logn)^Ω(1). If we impose an additional stability condition requiring the elements of each input sequence to appear in the same order in the output sequence, the time complexity of the problem becomes Θ(logn), even form=2. Stable merging is thus harder than nonstable merging.     

A Parallel Priority Queue with Constant Time Operations

We present a parallel priority queue that supports the following operations in constant time:parallel insertionof a sequence of elements ordered according to key,parallel decrease keyfor a sequence of elements ordered according to key,deletion of the minimum key element, anddeletion of an arbitrary element. Our data structure is the first to support multi-insertion and multi-decrease key in constant time. The priority queue can be implemented on the EREW PRAM and can perform any sequence ofnoperations inO(n) time andO(mlogn) work,mbeing the total number of keyes inserted and/or updated. A main application is a parallel implementation of Dijkstra's algorithm for the single-source shortest path problem, which runs inO(n) time andO(mlogn) work on a CREW PRAM on graphs withnvertices andmedges. This is a logarithmic factor improvement in the running time compared with previous approaches.     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

Matching with don't-cares and a small number of mismatches

In matching with don't-cares and k mismatches we are given a pattern of length m and a text of length n, both of which may contain don't-cares (a symbol that matches all symbols), and the goal is to find all locations in the text that match the pattern with at most k mismatches, where k is a parameter. We present new algorithms that solve this problem using a combination of convolutions and a dynamic programming procedure. We give randomized and deterministic solutions that run in time O(nk²logm) and O(nk³logm), respectively, and are faster than the most efficient extant methods for small values of k. Our deterministic algorithm is the first to obtain an O(polylog(k)⋅nlogm) running time.     

A chained-matrices approach for parallel computation of continued fractions and its applications

A chained-matrices approach for parallel computing thenth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction inO(logn) time on the EREW PRAM model or a network withO(n/logn) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as ande, inO(logm) time by usingO(m/logm) processors for a result withm-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the generalmth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.This work was supported in part by National Science Council of the Republic of China under Contract NSC 77-0408-E002-09.     

Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n ²) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n ²) time, improving earlierO(n ² logn) results.     

Fast heuristic algorithms for rectilinear steiner trees

A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n ²) total time. However, it is shown that the latter approach runs inO(n ^3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366.     

Decremental 2- and 3-connectivity on planar graphs

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log² n) time. This givesO(log² n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Project ALCOM II (contract No. 7141) and Project ASMICS. A preliminary version of this paper appears in [12].Partially supported by a CNR Fellowship. Work done while the author was visiting Columbia University.On leave from IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USA.     

A faster parallel algorithm for a matrix searching problem

We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n²/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)²) time withO(n²/(log logn)² processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Part of the research was done while the author was at Princeton University, visiting the DIMACS center.     

Selection, Routing, and Sorting on the Star Graph

We consider the problems of selection, routing, and sorting on ann-star graph (withn! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a “(k, 1,k) chain network”) of the star graph which enables us to design efficient algorithms for the above mentioned problems. We present an algorithm that performs a sequence ofnprefix computations inO(n²) time. This algorithm is used as a subroutine in our other algorithms. We also show that sorting can be performed on then-star graph in timeO(n³) and that selection of a set of uniformly distributednkeys can be performed inO(n²) time with high probability. Finally, we also present a deterministic (nonoblivious) routing algorithm that realizes any permutation inO(n³) steps on then-star graph. There exists an algorithm in the literature that can perform a single prefix computation inO(nlgn) time. The best-known previous algorithm for sorting has a run time ofO(n³lgn) and is deterministic. To our knowledge, the problem of selection has not been considered before on the star graph.     

Solving shortest paths efficiently on nearly acyclic directed graphs

Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in O(mn) worst-case time, which allowed it to be integrated as part of an O(mn+nrlogr) time all-pairs algorithm. Here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just O(m) time. This can be integrated as part of the O(m+rlogr) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in O(m) time and included as part of the O(m+rlogr) time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from O(mn+nr²) to O(mn+r³).     

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.     

An algorithm for segment-dragging and its implementation

Given a collection of points in the plane, pick an arbitrary horizontal segment and move it vertically until it hits one of the points (if at all). This form ofsegment-dragging is a common operation in computer graphics and motion-planning, it can also serve as a building block for multidimensional data structures. This note describes a new approach to segment-dragging which yields a simple and efficient solution. The data structure requiresO(n) storage andO(n logn) preprocessing time, and each query can be answered inO(logn) time, wheren is the number of points in the collection. The method is best understood as the end result of a sequence of transformations applied to a simple but inefficient starting solution.This work was started while the author was a visiting professor at Ecole Normale Supérieure, Paris, France.     

Minimum area circumscribing Polygons

We show that the smallestk-gon circumscribing a convexn-gon can be computed inO(n ² logn logk) time.     

Representing shared data on distributed-memory parallel computers

The problem of representing a setU≜{u ₁,...,u _m} of read-write variables on ann-node distributed-memory parallel computer is considered. It is shown thatU can be represented among then nodes of a variant of the mesh of trees usingO((m/n) polylog(m/n)) storage per node such that anyn-tuple of variables may be accessed inO(logn (log logn)²) time in the worst case form polynomial inn. This work was supported in part by the Joint Services Electronics Program under Contract F49620-87-C-0044 and by IBM under Agreement 12060043. Earlier versions of these results appeared in theProceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, October 1989 and in theProceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, July 1990.     

The optimal binary search tree for Andersson's search algorithm

Andersson [1] presented a search algorithm for binary search trees that uses only two-way key comparisons by deferring equality comparisons until the leaves are reached. The use of a different search algorithm means that the optimal tree for the traditional search algorithm, which has been shown to be computable inO(n ²) time by Knuth [3], is not optimal with respect to the different search algorithm. This paper shows that the optimal binary search tree for Andersson's search algorithm can be computed inO(nlogn) time using existing algorithms for the special case of zero successful access frequencies, such as the Hu-Tucker algorithm [2].     

The complexity of on-line simulations between multidimensional turing machines and random access machines

To study different implementations of arrays, we present four results on the time complexities of on-line simulations between multidimensional Turing machines and random access machines (RAMs). First, everyd-dimensional Turing machine of time complexityt can be simulated by a log-cost RAM running inO(t(logt)^1–(1/d)(log logt)^1/d) time. Second, everyd-dimensional Turing machine of time complexityt can be simulated by a unit-cost RAM running inO(t/(logt)^1/d) time, provided that the input length iso(t/(logt)^1/d). Third, there is a log-cost RAMR of time complexityO(n), wheren is the input length, such that, for anyd-dimensional Turing machineM that simulatesR on-line,M requires (n ^{1 + (1/d)})/(logn(log logn)^{1 + (1/d)})) time. Fourth, every unit-cost RAM of time complexityt can be simulated by ad-dimensional Turing machine inO(t ²(logt)^1/2) time ifd = 2, and inO(t ²) time ifd 3. This result uses the weight-balanced trees of Nievergelt and Reingold.This paper was prepared while M. C. Loui was visiting the National Science Foundation in Washington, DC, and the Institute for Advanced Computer Studies, University of Maryland, College Park, MD. The views, opinions, and conclusions in this paper are those of the authors and should not be construed as an official position of the National Science Foundation, Department of Defense, U.S. Air Force, or any other U.S. government agency. The research of M. C. Loui was supported by the National Science Foundation under Grant CCR-8922008.