158 citations · 543 across the 80 of their papers we have counts for
12 papers · 1 filter
Distinct distances between points and lines
Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu +1
We show that for points and lines in the real plane, the number of distinct distances between the points and the lines is , as long as $m^{1/2}\le n\le m…
Incidences with curves in R^d
Micha Sharir, Adam Sheffer, Noam Solomon
We prove that the number of incidences between points and bounded-degree curves with degrees of freedom in is \[ I(m,n) =O\left(m^{\frac{k}{dk-d+1}+\var…
Improved Bounds for 3SUM, -SUM, and Linear Degeneracy
Omer Gold, Micha Sharir
Given a set of real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Grønlund and Pettie [FOCS'14], a sim…
Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions
Boris Aronov, Micha Sharir
Given non-vertical lines in 3-space, their vertical depth (above/below) relation can contain cycles. We show that the lines can be cut into $O(n^{3/2}\mathop{\mathrm{polylog}}…
Delaunay Triangulations of Degenerate Point Sets
Michael Khanimov, Micha Sharir
The Delaunay triangulation (DT) is one of the most common and useful triangulations of point sets in the plane. DT is not unique when is degenerate, specifically when it co…
On the number of unit-area triangles spanned by convex grids in the plane
Orit E. Raz, Micha Sharir, Ilya D. Shkredov
A finite set of real numbers is called convex if the differences between consecutive elements form a strictly increasing sequence. We show that, for any pair of convex sets $A, B\s…