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 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 parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors 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, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.     

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.     

Optimal parallel verification of minimum spanning trees in logarithmic time

We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run inO(logn) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan. Research partially supported by a National Science Foundation Graduate Fellowship and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648. Research at Princeton University was partially supported by the National Science Foundation, Grant No. CCR-8920505, the Office of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648.     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ^d so that, given any query simplexq, the points inP q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ¹⁺/m ^1/d ) query time afterO(m ¹⁺) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+) storage for any fixed > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.A preliminary version of this paper has appeared in theProceedings of the Sixth Annual ACM Symposium on Computational Geometry, June 1990, pp. 23–33. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917 and NSF Grant CCR-90-02352. Work on this paper by Micha Sharir has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-8901484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Emo Welzl has been supported by Deutsche Forschungsgemeinschaft Grant We 1265/1–2. Micha Sharir and Emo Welzl have also been supported by a grant from the German-Israeli Binational Science Foundation. Last but not least, all authors thank DIMACS, an NSF Science and Technology Center, for additional support under Grant STC-88-09648.     

Optimal cooperative search in fractional cascaded data structures

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search.An earlier version of this work appears inProceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 307–316. The first author's support was provided in part by National Science Foundation Grant CCR-9007851, by the U.S. Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225. This research was performed while the second author was at Brown University. Support was provided in part by an NSF Presidential Young Investigator Award CCR-9047466, with matching funds from IBM, by National Science Foundation Grant CCR-9007851, by the U.S. Army Research Office under Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225.     

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.     

Selecting distances in the plane

We present a randomized algorithm for computing the kth smallest distance in a set ofn points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n^4/3 log^8/3 n). The algorithm can also be made deterministic, using a more complicated technique, with only a slight increase in its running time. A much simpler deterministic version of our procedure runs in time O(n^3/2 log^5/2 n). All versions improve the previously best-known upper bound ofO(@#@ n^9/5 log^4/5 n) by Chazelle [Ch]. A simpleO(n logn)-time algorithm for computing an approximation of the median distance is also presented.Part of this work was done while the first two authors were visting DIMACS, Rutgers University, New Brunswick, NJ. Work by the first three authors has been partly supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. Work by the second author has also been supported by National Security Agency Grant MDA 904-89-H-2030. Work by the third author has also been supported by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

A modular drinking philosophers algorithm

Summary A variant of the drinking philosophers algorithm of Chandy and Misra is described and proved correct in a modular way. The algorithm of Chandy and Misra is based on a particular dining philosophers algorithm and relies on certain properties of its implementation. The drinking philosophers algorithm presented in this paper is able to use an arbitrary dining philosophers algorithm as a subroutine; nothing about the implementation needs to be known, only that it solves the dining philosophers problem. An important advantage of this modularity is that by substituting a more time-efficient dining philosophers algorithm than the one used by Chandy and Misra, a drinking philosophers algorithm withO(1) worst-case waiting time is obtained, whereas the drinking philosophers algorithm of Chandy and Misra hasO(n) worst-case waiting time (forn philosophers). Careful definitions are given to distinguish the drinking and dining philosophers problems and to specify varying degrees of concurrency. Jennifer L. Welch received her B.A. in 1979 from the University of Texas at Austin, and her S.M. and Ph.D. from the Massachusetts Institute of Technology in 1984 and 1988 respectively. She has been a member of technical staff at GTE Laboratories Incorporated in Waltham, Massachusetts and an assistant professor at the University of North Carolina at Chapel Hill. She is currently an assistant professor at Texas A&M University. Her research interests include algorithms and lower bounds for distributed computing.Much of this work was performed while this author was at the Laboratory for Computer Science, Massachusetts Institute of Technology, supported by the Advanced Research Projects Agency of the Department of Defense under contract N00014-83-K-0125, the National Science Foundation under grants DCR-83-02391 and CCR-86-11442, the Office of Army Research under contract DAAG29-84-K-0058, and the Office of Naval Research under contract N00014-85-K-0168. This author was also supported in part by NSF grant CCR-9010730, an IBM Faculty Development Award, and NSF Presidential Young Investigator Award CCR-9158478This author was supported by the Office of Naval Research under contract N00014-91-J-1046, the Advanced Research Projects Agency of the Department of Defense under contract N00014-89-J-1988, and the National Science Foundation under grant CCR-89-15206. The photograph and autobiography of Professor N.A. Lynch were published in Volume 6, No. 2, 1992 on page 121     

Efficient PRAM simulation on a distributed memory machine

We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. Thedelay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of anm processor PRAM on ann processor DMM will necessarily have delay at leastm/n. A randomized simulation is calledtime-processor optimal if the delay isO(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delayO(log log(n) log*(n)). The best previous simulations use a simpler scheme based on hashing and have much larger delay: (log(n)/log log(n)) for the simulation of an n processor PRAM on ann processor DMM, and (log(n)) in the case where the simulation is time-processor optimal.Our simulations use several (two or three) hash functions to distribute the shared memory among the memory modules of the PRAM. The stochastic processes modeling the behavior of our algorithms and their analyses based on powerful classes of universal hash functions may be of independent interest.Research partially supported by NSF/DARPA Grant CCR-9005448. Work was done while at the University of California at Berkeley and the International Computer Science Institute, Berkeley, CA.Research partially supported by National Science Foundation Operating Grant CCR-9016468, National Science Foundation Operating Grant CCR-9304722, United States-Israel Binational Science Foundation Grant No. 89-00312, United States-Israel Binational Science Foundation Grant No. 92-00226, and ESPRIT BR Grant EC-US 030.Part of work was done during a visit at the International Computer Science Institute at Berkeley; supported in part by DFG-Forschergruppe Effiziente Nutzung massiv paralleler Systeme, Teilprojekt 4, and by the Esprit Basic Research Action Nr. 7141 (ALCOM II).     

An optimal algorithm for shortest paths on weighted interval and circular-arc graphs,with applications

We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the interval endpoints. Our algorithm solves this problem optimally inO(n) time, wheren is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is anO(qn + n logn)-time algorithm for the minimum-weight circle-cover problem, whereq is the minimum number of arcs crossing any point on the circle; then logn term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were0(n logn) for this shortest paths problem, andO(qn logn) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar (logn)-factor improvements in other problems on such graphs.The research of M. J. Atallah was supported in part by the Leonardo Fibonacci Institute, Trento, Italy, by the Air Force Office of Scientific Research under Contract AFOSR-90-0107, and by the National Science Foundation under Grant CCR-9202807. D. Z. Chen's research was supported in part by the Leonardo Fibonacci Institute, Trento, Italy. The research of D. T. Lee was supported in part by the Leonardo Fibonacci Institute, Trento, Italy, by the National Science Foundation, and the Office of Naval Research under Grants CCR-8901815, CCR-9309743, and N00014-93-1-0272.     

An improved technique for output-sensitive hidden surface removal

We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n^4/3 log^2.89 n +k ^3/5 n ^{4/5 +} for any > 0. The method is based on a new technique for tracing the visible contours using ray shooting.Work by the first author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under Contract No. 3075 (project ALCOM). Work by the second author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD-the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers, and Communication administered by the Israeli Academy of Sciences. A preliminary version of this paper appeared as part of the conference proceedings paper [17].     

Lazy structure sharing for query optimization

We studylazy structure sharing as a tool for optimizing equivalence testing on complex data types. We investigate a number of strategies for implementing lazy structure sharing and provide upper and lower bounds on their performance (how quickly they effect ideal configurations of our data structure). In most cases when the strategies are applied to a restricted case of the problem, the bounds provide nontrivial improvements over the naïve linear-time equivalence-testing strategy that employs no optimization. Only one strategy, however, which employs path compression, seems promising for the most general case of the problem.Work completed while at Princeton University and supported by a Fannie and John Hertz Foundation Fellowship, National Science Foundation Grant No. CCR-8920505, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) under NSF-STC-91-19999.Work completed while at Princeton University and DIMACS and supported by DIMACS under NSF-STC-91-19999.Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, the Office of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS under NSF-STC-91-19999.     

Simulating BPP using a general weak random source

We show how to simulate BPP and approximation algorithms in polynomial time using the output from a -source. A -source is a weak random source that is asked only once forR bits, and must output anR-bit string according to some distribution that places probability no more than 2^–R on any particular string. We also give an application to the unapproximability of MAX CLIQUE.This paper appeared in preliminary form in theProceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 79–89. Most of this research was done while the author was at U.C. Berkeley, and supported by an AT&T Graduate Fellowship, NSF PYI Grant No. CCR-8896202, and NSF Grant No. IRI-8902813. Part of this research was done while the author was at MIT, supported by an NSF Postdoctoral Fellowship, NSF Grant No. 92-12184 CCR, and DARPA Grant No. N00014-92-J-1799. Part of this research was done at UT Austin, where the author was supported by NSF NYI Grant No. CCR-9457799.     

Randomized incremental construction of Delaunay and Voronoi diagrams

In this paper we give a new randomized incremental algorithm for the construction of planar Voronoi diagrams and Delaunay triangulations. The new algorithm is more on-line than earlier similar methods, takes expected timeO(ngn) and spaceO(n), and is eminently practical to implement. The analysis of the algorithm is also interesting in its own right and can serve as a model for many similar questions in both two and three dimensions. Finally we demonstrate how this approach for constructing Voronoi diagrams obviates the need for building a separate point-location structure for nearest-neighbor queries.Leonidas Guibas and Micha Sharir wish to acknowledge the generous support of the DEC Systems Research Center in Palo Alto, California, where some of this work was carried out. Donald Knuth has been supported by NSF Grant CCR-86-10181. Micha Sharir has been supported by NSF Grant CCR-89-01484, ONR Grant N00014-K-87-0129, the U.S.-Israeli Binational Science Foundation, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

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].     

Parallel computational geometry of rectangles

Rectangles in a plane provide a very useful abstraction for a number of problems in diverse fields. In this paper we consider the problem of computing geometric properties of a set of rectangles in the plane. We give parallel algorithms for a number of problems usingn processors wheren is the number of upright rectangles. Specifically, we present algorithms for computing the area, perimeter, eccentricity, and moment of inertia of the region covered by the rectangles inO(logn) time. We also present algorithms for computing the maximum clique and connected components of the rectangles inO(logn) time. Finally, we give algorithms for finding the entire contour of the rectangles and the medial axis representation of a givenn × n binary image inO(n) time. Our results are faster than previous results and optimal (to within a constant factor).The work of Sung Kwan Kim was supported by NSF Grant CCR-87-03196 and the work of D. M. Mount was partially supported by National Science Foundation Grant CCR-89-08901.     

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.