Home

Micha Sharir

  1. Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique.

    Tue, 03/01/2011 - 16:01 — SomNambul
    Authors: Micha Sharir, Haim Kaplan, Jiří Matoušek
    Subjects: Combinatorics
    Abstract

    Recently Guth and Katz \cite{GK2} invented, as a step in their nearly
    complete solution of Erd\H{o}s's distinct distances problem, a new method for
    partitioning finite point sets in $\R^d$, based on the Stone--Tukey polynomial
    ham-sandwich theorem. We apply this method to obtain new and simple proofs of
    two well known results: the Szemer\'edi--Trotter theorem on incidences of
    points and lines, and the existence of spanning trees with low crossing
    numbers. Since we consider these proofs particularly suitable for teaching, we
    aim at self-contained, expository treatment.

  2. Counting Plane Graphs: Flippability and its Applications.

    Mon, 12/06/2010 - 16:01 — SomNambul
    Authors: Micha Sharir, Csaba D. Tóth, Adam Sheffer, Emo Welzl, Michael Hoffmann
    Subjects: Discrete Mathematics
    Abstract

    We generalize the notions of flippable and simultaneously-flippable edges in
    a triangulation of a set S of points in the plane, into so called pseudo
    simultaneously-flippable edges. Such edges are related to the notion of convex
    decompositions spanned by S.

  3. A Kinetic Triangulation Scheme for Moving Points in The Plane.

    Fri, 05/07/2010 - 15:02 — SomNambul
    Authors: Micha Sharir, Haim Kaplan, Natan Rubin
    Subjects: Computational Geometry
    Abstract

    We present a simple randomized scheme for triangulating a set $P$ of $n$
    points in the plane, and construct a kinetic data structure which maintains the
    triangulation as the points of $P$ move continuously along piecewise algebraic
    trajectories of constant description complexity. Our triangulation scheme
    experiences an expected number of $O(n^2\beta_{s+2}(n)\log^2n)$ discrete
    changes, and handles them in a manner that satisfies all the standard
    requirements from a kinetic data structure: compactness, efficiency, locality
    and responsiveness.

  4. Incidences in Three Dimensions and Distinct Distances in the Plane.

    Fri, 05/07/2010 - 15:02 — SomNambul
    Authors: Micha Sharir, György Elekes
    Subjects: Computational Geometry
    Abstract

    We first describe a reduction from the problem of lower-bounding the number
    of distinct distances determined by a set $S$ of $s$ points in the plane to an
    incidence problem between points and a certain class of helices (or parabolas)
    in three dimensions. We offer conjectures involving the new setup, but are
    still unable to fully resolve them.

  5. An Improved Bound on the Number of Unit Area Triangles.

    Wed, 01/27/2010 - 16:01 — SomNambul
    Authors: Micha Sharir, Roel Apfelbaum
    Subjects: Computational Geometry
    Abstract

    We show that the number of unit-area triangles determined by a set of $n$
    points in the plane is $O(n^{9/4+\epsilon})$, for any $\epsilon>0$, improving
    the recent bound $O(n^{44/19})$ of Dumitrescu et al.

  6. Counting Triangulations of Planar Point Sets.

    Wed, 11/18/2009 - 16:01 — SomNambul
    Authors: Micha Sharir, Adam Sheffer, Emo Welzl
    Subjects: Discrete Mathematics
    Abstract

    We study the maximal number of triangulations that a planar set of $n$ points
    can have, and show that it is at most $30^n$. This new bound is achieved by a
    careful optimization of the charging scheme of Sharir and Welzl (2006), which
    has led to the previous best upper bound of $43^n$ for the problem.

  7. Relative $(p,\epsilon)$-Approximations in Geometry.

    Fri, 09/04/2009 - 12:10 — SomNambul
    Authors: Sariel Har-Peled, Micha Sharir
    Subjects: Computational Geometry
    Abstract

    We re-examine the notion of relative $(p,\eps)$-approximations, recently
    introduced in [CKMS06], and establish upper bounds on their size, in general
    range spaces of finite VC-dimension, using the sampling theory developed in
    [LLS01] and in several earlier studies [Pol86, Hau92, Tal94]. We also survey
    the different notions of sampling, used in computational geometry, learning,
    and other areas, and show how they relate to each other. We then give
    constructions of smaller-size relative $(p,\eps)$-approximations for range
    spaces that involve points and halfspaces in two and higher dimensions.

Math-arch

Syndicate content