Fréchet Embeddings of Negative Type Metrics

We show that every n-point metric of negative type (in particular, every n-point subset of L ₁) admits a Fréchet embedding into Euclidean space with distortion , a result which is tight up to the O(log log n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space. S. Arora supported by David and Lucile Packard Fellowship and NSF grant CCR-0205594. J.R. Lee supported by NSF grant CCR-0121555, NSF 0514993, NSF 0528414 and an NSF Graduate Research Fellowship.     

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m] ^d ={1,2,3,...,m} ^d that hits every combinatorial rectangle in [m] ^d of volume at least , i.e., every subset of [m] ^d the formR ₁×R ₂×...×R _d of size at least m ^d . The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Pseudorandom generators for space-bounded computation

Pseudorandom generators are constructed which convertO(SlogR) truly random bits toR bits that appear random to any algorithm that runs inSPACE(S). In particular, any randomized polynomial time algorithm that runs in spaceS can be simulated using onlyO(Slogn) random bits. An application of these generators is an explicit construction of universal traversal sequences (for arbitrary graphs) of lengthn ^O(logn).The generators constructed are technically stronger than just appearing random to spacebounded machines, and have several other applications. In particular, applications are given for deterministic amplification (i.e. reducing the probability of error of randomized algorithms), as well as generalizations of it.This work was done in the Laboratory for Computer Science, MIT, supported by NSF 865727-CCR and ARO DALL03-86-K-017     

Constructing arrangements optimally in parallel

We give two optimal parallel algorithms for constructing the arrangement ofn lines in the plane. The first nethod is quite simple and runs inO(log² n) time usingO(n ²) work, and the second method, which is more sophisticated, runs inO(logn) time usingO(n ²) work. This second result solves a well-known open problem in parallel computational geometry, and involves the use of a new algorithmic technique, the construction of an -pseudocutting. Our results immediately imply that the arrangement ofn hyperplanes in ^d inO(logn) time usingO(n ^d) work, for fixedd, can be optimally constructed. Our algorithms are for the CREW PRAM.This research was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092.     

Quasi-planar graphs have a linear number of edges

A graph is calledquasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph withn vertices isO(n).Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995.     

Approximation schemes for NP-hard geometric optimization problems: a survey

 Traveling Salesman, Steiner Tree, and many other famous geometric optimization problems are NP-hard. Since we do not expect to design efficient algorithms that solve these problems optimally, researchers have tried to design approximation algorithms, which can compute a provably near-optimal solution in polynomial time. We survey such algorithms, in particular a new technique developed over the past few years that allows us to design approximation schemes for many of these problems. For any fixed constant c> 0, the algorithm can compute a solution whose cost is at most (1 + c) times the optimum. (The running time is polynomial for every fixed c> 0, and in many cases is even nearly linear.) We describe how these schemes are designed, and survey the status of a large number of problems. Received: December 2, 2002 / Accepted: April 28, 2003 Published online: May 28, 2003 Supported by a David and Lucile Packard Fellowship, NSF grant CCR-0098180, NSF ITR grant CCR-0205594     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from 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.     

Vertical decompositions for triangles in 3-space

We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n ^2+ɛ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n ^2+ɛ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n ² logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ _q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ _q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm. Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10.     

A 2 + ɛ approximation algorithm for the k-MST problem

For any ɛ > 0 we give a (2 + ɛ)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + ɛ)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality. Research supported by NSF CAREER award NSF CCR-9502747, NSF grants CCR-0205594 and CCR-0098180, an Alfred Sloan Fellowship, and a Packard Fellowship. Research supported by an NSERC Discovery grant.     

A fast parallel algorithm to compute the rank of a matrix over an arbitrary field

It is shown that the rank of a matrix over an arbitrary field can be computed inO(log² n) time using a polynomial number of processors. Also appeared in ACM Symposium on Theory of Computing, May 28–30, 1986 Berkeley, California. Research supported by Miller Fellowship, University of California, Berkeley.     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

An optimal convex hull algorithm in any fixed dimension

We present a deterministic algorithm for computing the convex hull ofn points inE ^d in optimalO(n logn+n ^⌞d/2⌟ ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram ofn points ind-space in optimalO(n logn+n ^⌜d/2⌝ ) time. This research was supported in part by the National Science Foundation under Grant CCR-9002352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. A preliminary version of this paper has appeared in “An optimal convex hull algorithm and new results on cuttings”,Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science, October 1991, pp. 29–38. The convex hull algorithm given in the present paper, although similar in spirit, is considerably simpler than the one given in the proceedings.     

Almost tight upper bounds for the single cell and zone problems in three dimensions

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement ofn low-degree algebraic surface patches in 3-space. We show that this complexity isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. This extends several previous results, almost settles a 9-year-old open problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the overall complexity of all the three-dimensional cells of an arrangement ofn low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch σ (the so-calledzone of σ in the arrangement) isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. Work on this paper by the first author has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-111327, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Israel Science Fund administered by the Israeli Academy of Sciences.     

Approximating maximum independent sets by excluding subgraphs

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)²). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.A preliminary version of this paper appeared in [9].Supported in part by National Science Foundation Grant CCR-8902522 and PYI Award CCR-9057488.Research done at Rutgers University. Supported in part by Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) fellowship.     

A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

Vertical decomposition of arrangements of hyperplanes in four dimensions

We show that, for any collection ℋ ofn hyperplanes in ℜ⁴, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n ⁴ logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning them. Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University.     

Visibility and intersection problems in plane geometry

We develop new data structures for solving various visibility and intersection problems about a simple polygonP onn vertices. Among our results are a simpleO(n logn)-time algorithm for computing the illuminated subpolygon ofP from a luminous side, and anO(logn)-time algorithm for determining which side ofP is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing onP which takes timeO(n logn) and spaceO(n). The two main tools in attacking these problems are geometric duality on the two-sided plane and fractional cascading.Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8700917. A preliminary version of this paper was presented at the First Annual ACM Symposium on Computational Geometry, June 1985.     

The set union problem with dynamic weighted backtracking

We consider an extension of the set union problem, in which dynamic weighted backtracking over sequences of unions is permitted. We present a new data structure which can support each operation inO(logn) time in the worst case. We prove that this bound is tight for pointer based algorithms. Furthermore, we design a different data structure to achieve better amortized bounds. The space complexity of both our data structures isO(n). Motivations for studying this problem arise in logic programming memory management.Work partially supported by NSF Grant CCR-88-14977, by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (Project ALCOM), and by the Italian MURST Project Algoritmi e Strutture di Calcolo.Partially supported by an IBM Graduate Fellowship.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.