The only convex body with extremal distance from the ball is the simplex

We can extend the Banach-Mazur distance to be a distance between non-symmetric sets by allowing affine transformations instead of linear transformations. It was proved in [J] that for every convex bodyK we haved(K, D)≤n. It is proved that ifK is a convex body in ℝ ⁿ such thatd(K, D)=n, thenK is a simplex. This article is an M.Sc. thesis written under the supervision of E. Gluskin and V.D. Milman at Tel Aviv University. Partially supported by a G.I.F. grant.     

The Overlay of Minimization Diagrams in a Randomized Incremental Construction

In a randomized incremental construction of the minimization diagram of a collection of n hyperplanes in ℝ ^d , for d≥2, the hyperplanes are inserted one by one, in a random order, and the minimization diagram is updated after each insertion. We show that if we retain all the versions of the diagram, without removing any old feature that is now replaced by new features, the expected combinatorial complexity of the resulting overlay does not grow significantly. Specifically, this complexity is O(n ^⌊d/2⌋log n), for d odd, and O(n ^⌊d/2⌋), for d even. The bound is asymptotically tight in the worst case for d even, and we show that this is also the case for d=3. Several implications of this bound, mainly its relation to approximate halfspace range counting, are also discussed.     

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.     

Voronoi diagrams of random lines and flats

It is proved that, for any fixedd ≽ 3 and 0 ≤k ≤ d - 1, the expected combinatorial complexity of the Euclidean Voronoi diagram ofn random &-flats drawn independently from the uniform distribution onk-flats intersecting the unit ball in ℝ^d is Ξ(n ^d/(d-k)) asn → ∞. A by-product of the proof is a density transformation for integrating over sets ofd + 1k-flats in ℝ^d     

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 surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

On the concentration of eigenvalues of random symmetric matrices

It is shown that for every 1≤s≤n, the probability that thes-th largest eigenvalue of a random symmetricn-by-n matrix with independent random entries of absolute value at most 1 deviates from its median by more thant is at most 4e ⁻ t ²32 ^s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces. Research supported in part by a USA — Israel BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a USA — Israel BSF grant and by a Bergmann Memorial Grant.     

Efficient Algorithms for Maximum Regression Depth

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n ^d ) time and O(n ^d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog ² n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results. A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry (1999) M. van Kreveld partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number 642.065.503. J.S.B. Mitchell’s research largely conducted while the author was a Fulbright Research Scholar at Tel Aviv University. The author is partially supported by NSF (CCR-9504192, CCR-9732220), Boeing, Bridgeport Machines, Sandia, Seagull Technology, and Sun Microsystems. M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, 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 ESPRIT IV LTR project No. 21957 (CGAL), and by the Hermann Minkowski—MINERVA Center for Geometry at Tel Aviv University. J. Snoeyink supported in part by grants from NSERC, the Killam Foundation, and CIES while at the University of British Columbia.     

Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem

The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in ℝ ^d , incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radius r(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ ⁴/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(n ^Δ+1 dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space. An extended abstract appeared in ACM–SIAM Symposium on Discrete Algorithms, 2006. Work was done when J. Gao was with Center for the Mathematics of Information, California Institute of Technology. Work was done when M. Langberg was a postdoctoral scholar at the California Institute of Technology. Research supported in part by NSF grant CCF-0346991. Research of L.J. Schulman supported in part by an NSF ITR and the Okawa Foundation.     

Vertex Numbers of Weighted Faces in Poisson Hyperplane Mosaics

In the random mosaic generated by a stationary Poisson hyperplane process in ℝ ^d , we consider the typical k-face weighted by the j-dimensional volume of the j-skeleton (0≤j≤k≤d). We prove sharp lower and upper bounds for the expected number of its vertices.     

A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities

In this paper we consider the problem of bounding the Betti numbers, b _i (S), of a semi-algebraic set S⊂ℝ ^k defined by polynomial inequalities P ₁≥0,…,P _s ≥0, where P _i ∈ℝ[X ₁,…,X _k ], s<k, and deg (P _i )≤2, for 1≤i≤s. We prove that for 0≤i≤k−1,

Hausdorff measures of different dimensions are not Borel isomorphic

We show that Hausdorff measures of different dimensions are not Borel isomorphic; that is, the measure spaces (ℝ, B, H ^s ) and (ℝ, B, H ^t ) are not isomorphic if s ≠ t, s, t ∈ [0, 1], where B is the σ-algebra of Borel subsets of ℝ and H ^d is the d-dimensional Hausdorff measure. This answers a question of B. Weiss and D. Preiss. To prove our result, we apply a random construction and show that for every Borel function ƒ: ℝ → ℝ and for every d ∈ [0, 1] there exists a compact set C of Hausdorff dimension d such that ƒ(C) has Hausdorff dimension ≤ d. We also prove this statement in a more general form: If A ⊂ ℝⁿ is Borel and ƒ: A → ℝ^m is Borel measurable, then for every d ∈ [0, 1] there exists a Borel set B ⊂ A such that dim B = d·dim A and dim ƒ(B) ≤ d·dim ƒ (A). Partially supported by the Hungarian Scientific Research Fund grant no. T 49786.     

Convolution Estimates and Model Surfaces of Low Codimension

For k≥d/2 we give examples of measures on k-surfaces in ℝ ^d . These measures satisfy convolution estimates which are nearly optimal. The author was supported in part by NSF grant DMS-0552041.     

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.     

Discrete and Lexicographic Helly-Type Theorems

Helly’s theorem says that if every d+1 elements of a given finite set of convex objects in ℝ ^d have a common point, then there is a point common to all of the objects in the set. We define three new types of Helly theorems: discrete Helly theorems—where the common point should belong to an a-priori given set, lexicographic Helly theorems—where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We study the relations between the different types of the Helly theorems. We obtain several new discrete and lexicographic Helly numbers. An extended abstract containing parts of this work appeared in the proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science (FOCS) 2004. This work is part of the author’s Ph.D. thesis, prepared in the school of mathematical sciences at Tel Aviv University, under the supervision of Professor Arie Tamir.     

An elementary approach to lower bounds in geometric discrepancy

For eachd≥2, it is possible to placen points ind-space so that, given any two-coloring of the points, a half-space exists within which one color outnumbers the other by as much ascn ^1/2−1/2d , for some constantc>0 depending ond. This result was proven in a slightly weaker form by Beck and the bound was later tightened by Alexander. It was recently shown to be asymptotically optimal by Matoušek. We present a proof of the lower bound, which is based on Alexander's technique but is technically simpler and more accessible. We present three variants of the proof, for three diffrent cases, to provide more intuitive insight into the “large-discrepancy” phenomenon. We also give geometric and probabilistic interpretations of the technique. Work by Bernard Chazelle has been supported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. Work by Jiří Matoušek has been supported by Charles University Grant No. 351, by Czech Republic Grant GAČR 201/93/2167 and in part by DIMACS. Work by Micha Sharir has been supported by NSF Grant CCR-91-22103, by a Max-Planck Research Award, 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.     

Maximum principles for the polyharmonic equation on Lipschitz domains

The Agmon-Miranda maximum principle for the polyharmonic equations of all orders is shown to hold in Lipschitz domains in ℝ³. In ℝn,n≥4, the Agmon-Miranda maximum principle andL ^p-Dirichlet estimates for certainp>2 are shown to fail in Lipschitz domains for these equations. In particular if 4≤n≤2m+1 theL ^p Dirichlet problem for Δ ^m fails to be solvable forp>2(n−1)/(n−3). Supported in part by the NSF.     

Facet-reducing cuts of a convex polytope

We construct, for everyd>-4, ad-polytopeP⊂ℝ ^d , containing two verticesv andw such that no hyperplane of ℝ ^d containingv andw has more than one facet ofP in either of its closed half-spaces. The result shows that facet-reducing cuts containing a prespecified pair of vertices of a polytope, do not exist in general. This research was supported in part by an NSF Research Initiation Award.     

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.     

Relative mean curvature configurations for surfaces in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>, <Emphasis Type="Italic">n</Emphasis> ≥ 5

We define the relative mean curvature directions on surfaces immersed in ℝⁿ, n ≥ 4, generalizing the concept of mean curvature directions for surfaces in 4-space studied by Mello. We obtain their differential equations and study their corresponding generic configurations. *Work partially supported by DGCYT grant no. MTM2004-03244 and Unimontes-BR. †Work partially supported by DGCYT grant no. MTM2004-03244. ‡Work partially supported by DGCYT grant no. BFM2003-0203.