An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log² n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.This research was supported by NSF Grants CCR-9011214 and CCR-9205982.     

An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log² n) time withO(n ³) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

Balancing minimum spanning trees and shortest-path trees

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and a>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+2 times the shortest-path distance, and yet the total weight of the tree is at most 1+2/ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex.Current research supported by NSF Research Initiation Award CCR-9307462. This work was done while this author was supported by NSF Grants CCR-8906949, CCR-9103135, and CCR-9111348.Part of this work was done while this, author was at the University of Maryland Institute for Advanced Computer Studies (UMIACS) and supported by NSF Grants CCR-8906949 and CCR-9111348.     

Optimal parallel algorithms for point-set and polygon problems

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.The research of R. Cole was supported in part by NSF Grants CCR-8702271, CCR-8902221, and CCR-8906949, by ONR Grant N00014-85-K-0046, and by a John Simon Guggenheim Memorial Foundation fellowship. M. T. Goodrich's research was supported by the National Science Foundation under Grant CCR-8810568 and by the National Science Foundation and DARPA under Grant CCR-8908092.     

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 nearly optimal deterministic parallel Voronoi diagram algorithm

We describe ann-processor,O(log(n) log log(n))-time CRCW algorithm to construct the Voronoi diagram for a set ofn point-sites in the plane.A preliminary version of this paper was presented at the 17th EATCS ICALP meeting at Warwick, England, in July 1990.Supported by the US NSF under Grants CCR 890221 and CCR 8906949.Supported by the US NSF under Grants CCR 8810568, CCR-9003299, and IRI-9116843, and by the NSF and DARPA under Grant CCR 8908092.Supported by the EU Esprit program under BRAs 3075 (ALCOM) and 7141 (ALCOM II).     

The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.Richard Cole was supported in part by NSF Grants DCR-84-01633 and CCR-8702271, ONR Grant N00014-85-K-0046 and by an IBM faculty development award. Uzi Vishkin was supported in part by NSF Grants NSF-CCR-8615337 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046, by the Applied Mathematical Science subprogram of the office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077 and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities.     

Data structures and algorithms for the string statistics problem

Given a textstringx of lengthn, theMinimal Augmented Suffix Tree T (x) ofx is a digital-search index that returns, for anyquery stringw and in a number of comparisons bounded by the length ofw, the maximum number of nonoverlapping occurrences ofw inx. It is shown that, denoting the length ofx byn, T(x) can be built in timeO(n log² n) and spaceO(n logn), off-line on a RAM.This research was supported in part, through the Leonardo Fibonacci Institute, by the Istituto Trentino di Cultura, Trento, Italy.Additional support was provided by NSF Grants CCR-8900305 and CCR-9201078, by NATO Grant CRG 900293, by the National Research Council of Italy, and by the ESPRIT III Basic Research Programme of the EC under Contract No. 9072 (Project GEPPCOM).Additional support was provided by NSF Grant CCR-91-96176 and ONR Contract N 00014-91-J-4052, ARPA Order 2225.     

Can PAC learning algorithms tolerate random attribute noise?

This paper studies the robustness of PAC learning algorithms when the instance space is {0,1}ⁿ, and the examples are corrupted by purely random noise affecting only the attributes (and not the labels). Foruniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that PAC learns monomials for any (unknown) noise rate less than ₂ ¹ . Contrasting this positive result, we show thatproduct random attribute noise, where each attributei is flipped randomly and independently with its own probability p_i, is nearly as harmful as malicious noise-no algorithm can tolerate more than a very small amount of such noise.The research of S. A. Goldman was supported in part by a GE Foundation Junior Faculty grant and NSF Grant CCR-9110108. Part of this research was conducted while the author was at the M.I.T. Laboratory for Computer Science and supported by NSF Grant DCR-8607494 and a grant from the Siemens Corporation. The research of R. H. Sloan was supported in part by NSF Grant CCR-9108753. Part of this research was conducted while the author was at Harvard and supported by ARO Grant DAAL 03-86-K-0171.     

Optimal edge ranking of trees in polynomial time

An edge ranking of a graph is a labeling of the edges using positive integers such that all paths between two edges with the same label contain an intermediate edge with a higher label. An edge ranking isoptimal if the highest label used is as small as possible. The edge-ranking problem has applications in scheduling the manufacture of complex multipart products; it is equivalent to finding the minimum height edge-separator tree. In this paper we give the first polynomial-time algorithm to find anoptimal edge ranking of a tree, placing the problem inP. An interesting feature of the algorithm is an unusual greedy procedure that allows us to narrow an exponential search space down to a polynomial search space containing an optimal solution. AnNC algorithm is presented that finds an optimal edge ranking for trees of constant degree. We also prove that a natural decision problem emerging from our sequential algorithm isP-complete.The research of P. de la Torre was partially supported by NSF Grant CCR-9010445. R. Greenlaw's research was partially supported by NSF Grant CCR-9209184. The research of A. A. Schäffer was partially supported by NSF Grant CCR-9010534.Subsequent to the acceptance of this paper, Zhou and Nishizeki found faster algorithms for optimal edge ranking of trees, first reducing the time toO(n²) [22] and then toO(n logn) [23].     

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.     

Parallel methods for visibility and shortest-path problems in simple polygons

In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.This research was announced in preliminary form in theProceedings of the 6th ACM Symposium on Computational Geometry, 1990, pp. 73–82. The research of Michael T. Goodrich was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092.     

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.     

Planar geometric location problems

We present anO(n ² log³ n) algorithm for the two-center problem, in which we are given a setS ofn points in the plane and wish to find two closed disks whose union containsS so that the larger of the two radii is as small as possible. We also give anO(n ² log⁵ n) algorithm for solving the two-line-center problem, where we want to find two strips that coverS whose maximum width is as small as possible. The best previous solutions of both problems requireO(n ³) time.Pankaj Agarwal has been supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), an NSF Science and Technology Center, under Grant STC-88-09648. Micha Sharir has been supported by the Office of Naval Research under Grants N00014-89-J-3042 and N00014-90-J-1284, by the National Science Foundation under Grant CCR-89-01484, by DIMACS, and by grants from the US-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. A preliminary version of this paper has appeared inProceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 449–458.     

A linear-time algorithm for finding an ambitus

We devise a linear-time algorithm for finding an ambitus ín an undirected graph. An ambitus is a cycle in a graph containing two distinguished vertices such that certain different groups of bridges (calledB ^itp-,B ^itQ-, andB ^itPQ-bridges) satisfy the property that a bridge in one group does not interlace with any bridge in the other groups. Thus, an ambitus allows the graph to be cut into pieces, where, in each piece, certain graph properties may be investigated independently and recursively, and then the pieces can be pasted together to yield information about these graph properties in the original graph. In order to achieve a good time-complexity for such an algorithm employing the divide-and-conquer paradigm, it is necessary to find an ambitus quickly. We also show that, using ambitus, linear-time algorithms can be devised for abiding-path-finding and nonseparating-induced-cycle-finding problems.The research of B. Mishra was supported in part by National Science Foundation Grants DMS-8703458 and CCR-9002819. R. E. Tarjan's research at Princeton University was partially supported by DIMACS, a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648, and by National Science Foundation Grant CCR-8929505.     

Blocking for external graph searching

In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.Support was provided in part by an IBM Graduate Fellowship, by NSF Research Grants CCR-9007851 and IRI-9116451, and by Army Research Office Grant DAAL03-91-G-0035.Support was provided in part by NSF Grants CCR-9003299, CCR-9300079, and IRI-9116843, and by NSF/DARPA Grant CCR-8908092.Support was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, and by Army Research Office Grant DAAL03-91-G-0035.     

An algorithm for constructing gr?bner bases from characteristic sets and its application to geometry

In Ritt's method, a prime ideal is given by a characteristic set. A characteristic set of a prime ideal is generally not a set of generators of this ideal. In this paper we present a simple algorithm for constructing Gröbner bases of a prime ideal from its characteristic set. We give a method for finding new theorems in geometry as an application of this algorithm.The first author was supported by NSF Grants Nos. DCR-8503498 and CCR-8702108. The computer facility was supported by the NSF/CER Grant at the University of Texas.     

Primitives for asynchronous list compression

In this paper we study the problem of asynchronous processors traversing a list with path compression. We show that if an atomic splice operation is available, the worst-case work forp processors traversing a list of length h is (np ^1/2). The splice operation can be generalized to removek elements from the list. For thek-splice operation the worst-case work is (np ^1/ k+1).This research was supported by an NSF Presidential Young Investigator Award CCR-8657562, Digital Equipment Corporation, NSF CER Grant CCR-861966, and NSF/Darpa Grant CCR-8907960. A preliminary version of this paper was presented at the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures.