158 citations · 543 across the 80 of their papers we have counts for
5 papers · 2 filters
The 2-Center Problem in Three Dimensions
Pankaj K. Agarwal, Rinat Ben Avraham, Micha Sharir
Let P be a set of n points in R^3. The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present two randomized algorithms for comput…
Improved Bounds for Geometric Permutations
Natan Rubin, Haim Kaplan, Micha Sharir
We show that the number of geometric permutations of an arbitrary collection of pairwise disjoint convex sets in , for , is , improvin…
Incidences in Three Dimensions and Distinct Distances in the Plane
György Elekes, Micha Sharir
We first describe a reduction from the problem of lower-bounding the number of distinct distances determined by a set of points in the plane to an incidence problem between…
A Kinetic Triangulation Scheme for Moving Points in The Plane
Haim Kaplan, Natan Rubin, Micha Sharir
We present a simple randomized scheme for triangulating a set of points in the plane, and construct a kinetic data structure which maintains the triangulation as the points…
An Improved Bound on the Number of Unit Area Triangles
Roel Apfelbaum, Micha Sharir
We show that the number of unit-area triangles determined by a set of points in the plane is , for any , improving the recent bound of Dumitre…