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.     

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.     

Improved bounds on weak ε-nets for convex sets

LetS be a set ofn points in ℝ ^d . A setW is aweak ε-net for (convex ranges of)S if, for anyT⊆S containing εn points, the convex hull ofT intersectsW. We show the existence of weak ε-nets of size , whereβ ₂=0,β ₃=1, andβ _d ≈0.149·2 ^d-1(d-1)!, improving a previous bound of Alonet al. Such a net can be computed effectively. We also consider two special cases: whenS is a planar point set in convex position, we prove the existence of a net of sizeO((1/ε) log^1.6(1/ε)). In the case whereS consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of sizeO(1/ε), which improves a previous bound of Capoyleas. Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Michelangelo Grigni has been supported by NSERC Operating Grants and NSF Grant DMS-9206251. Work by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Emo Welzl and Micha Sharir has been supported by a grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Work by Micha Sharir has also been supported by NSF Grant CCR-91-22103, and by a grant from the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Points and triangles in the plane and halving planes in space

We prove that for any setS ofn points in the plane andn ^3−α triangles spanned by the points inS there exists a point (not necessarily inS) contained in at leastn ^3−3α/(c log⁵ n) of the triangles. This implies that any set ofn points in three-dimensional space defines at most halving planes. Work on this paper by Boris Aronov and Rephael Wenger has been supported by DIMACS under NSF Grant STC-88-09648. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-87-14565. Micha Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

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.     

A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment

We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn) ^2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion-planning problem, within the same running time. Work on this paper by Dan Halperin 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 Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, 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. A preliminary and extended version of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University.     

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.     

Algorithms for ham-sandwich cuts

Given disjoint setsP ₁,P ₂, ...,P _d inR ^d withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP _i . We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR ^d−1 . With the current estimates, we get complexity close toO(n ^3/2 ) ford=3, roughlyO(n ^8/3 ) ford=4, andO(n ^d−1−a(d) ) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR ³ when the three sets are suitably separated. A preliminary version of the results of this paper appeared in [16] and [17]. Part of this research by J. Matoušek was done while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

On the size of the set of points where the metric projection exists

In this paper we answer in the negative a question due to J. P. R. Christensen about almost everywhere existence of nearest points using a decomposition of ℓ₂ due to J. Matoušek and E. Matoušková. We also formulate a similar question about almost everywhere existence of farthest points and answer it in the negative. The author was supported by the grant GAČR 201/00/0767 (from the Grant Agency of the Czech Republic).     

Almost optimal set covers in finite VC-dimension

We give a deterministic polynomial-time method for finding a set cover in a set system (X, ℛ) of dual VC-dimensiond such that the size of our cover is at most a factor ofO(d log(dc)) from the optimal size,c. For constant VC-dimensional set systems, which are common in computational geometry, our method gives anO(logc) approximation factor. This improves the previous Θ(log⋎X⋎) bound of the greedy method and challenges recent complexity-theoretic lower bounds for set covers (which do not make any assumptions about the VC-dimension). We give several applications of our method to computational geometry, and we show that in some cases, such as those arising in three-dimensional polytope approximation and two-dimensional disk covering, we can quickly findO(c)-sized covers. The first author was supported in part by NSF Grant CCR-90-02352 and Ecole Normale Supérieure. The second author's research was supported by the NSF and DARPA under Grant CCR-8908092, and by the NSF under Grants IRI-9116843 and CCR-9300079.     

Lower bounds for off-line range searching

This paper proves three lower bounds for variants of the following rangesearching problem: Given n weighted points inR ^d andn axis-parallel boxes, compute the sum of the weights within each box: (1) if both additions and subtractions are allowed, we prove that Ω(n log logn) is a lower bound on the number of arithmetic operations; (2) if subtractions are disallowed the lower bound becomes Ω(n(logn/loglogn)^d-1), which is nearly optimal; (3) finally, for the case where boxes are replaced by simplices, we establish a quasi-optimal lower bound of Ω(n^2-2/(d+1))/polylog(n). A preliminary version of this paper appeared inProc. 27th Ann. ACM Symp. on Theory of Computing, May 1995, pp. 733–740. This work was supported in part by NSF Grant CCR-93-01254 and the Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc.     

Applications of a new space-partitioning technique

We present several applications of a recent space-partitioning technique of Chazelle, Sharir, and Welzl (Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 23–33). Our results include efficient algorithms for output-sensitive hidden surface removal, for ray shooting in two and three dimensions, and for constructing spanning trees with low stabbing number.Work on this paper has been supported by DIMACS, an NSF Science and Technology Center, under Grant STC-88-09684. The second author has been supported by Office of Naval Research Grants N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation 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.     

On Overlays and Minimization Diagrams

The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ ^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ ^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed. Work by V. Koltun was supported by NSF CAREER award CCF-0641402. Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Castles in the air revisited

We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ ^d isO(n ^d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more than one “side” isO(n ^d−1 logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n ^d−1 log² n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement. Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

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.     

An upper bound on the number of planarK-sets

Given a setS ofn points, a subsetX of sizek is called ak-set if there is a hyperplane that separatesX fromS–X. We prove thatO(nk/log*k) is an upper bound for the number ofk-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log*k.The research of J. Pach was supported in part by NSF Grant CCR-8901484 and by Grant OTKA-1418 from the Hungarian Foundation for Scientific Research. The research of W. Steiger and E. Szemerédi was supported in part by NSF Grant CCR-8902522. All authors express gratitude to the NSF DIMACS Center at Rutgers.     

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.     

On visibility and covering by convex sets

A setX⊆ℝ ^d isn-convex if among anyn of its points there exist two such that the segment connecting them is contained inX. Perles and Shelah have shown that any closed (n+1)-convex set in the plane is the union of at mostn ⁶ convex sets. We improve their bound to 18n ³, and show a lower bound of order Ω(n ²). We also show that ifX⊆ℝ² is ann-convex set such that its complement has λ one-point path-connectivity components, λ<∞, thenX is the union ofO(n ⁴+n ²λ) convex sets. Two other results onn-convex sets are stated in the introduction (Corollary 1.2 and Proposition 1.4). Research supported by Charles University grants GAUK 99/158 and 99/159, and by U.S.-Czechoslovak Science and Technology Program Grant No. 94051. Part of the work by J. Matoušek was done during the author’s visits at Tel Aviv University and The Hebrew University of Jerusalem. Part of the work by P. Valtr was done during his visit at the University of Cambridge supported by EC Network DIMANET/PECO Contract No. ERBCIPDCT 94-0623.     

Almost tight upper bounds for lower envelopes in higher dimensions

We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope ofn such surface patches isO(n ^d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope isO(n ^d-2λ _q (n)) for some constantq depending on the shape and degree of the surfaces (where λ _q (n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running timeO(n ^2+∈), and give several applications of the new bounds. Work on this paper has been supported by NSF Grant CCR-91-22103, 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 Fund for Basic Research administered by the Israeli Academy of Sciences.     

Circles through two points that always enclose many points

This paper proves that any set of n points in the plane contains two points such that any circle through those two points encloses at least points of the set. The main ingredients used in the proof of this result are edge counting formulas for k-order Voronoi diagrams and a lower bound on the minimum number of semispaces of size at most k.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565, by the second author has been partially supported by the Digital Equipment Corporation, by the fourth author has been partially supported by the Office of Naval Research under Grant N00014-86K-0416.