M. Sharir

activity

20032026

most citedIncidences between points and lines on a two-dimensional variety

158 citations · 543 across the 80 of their papers we have counts for

collaborators

Showing 2016Show all

14 papers · 1 filter

math.CO2016

Distinct distances between a collinear set and an arbitrary set of points

Ariel Bruner, Micha Sharir

We consider the number of distinct distances between two finite sets of points in $R^{k}$ , for any constant dimension $k \geq 2$ , where one set $P_{1}$ consists of $n$ points on a…

math.CO2016

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances

Micha Sharir, Noam Solomon

We study a wide spectrum of incidence problems involving points and curves or points and surfaces in $R^{3}$ . The current (and in fact the only viable) approach to such probl…

math.CO2016

Incidences between points and lines on two- and three-dimensional varieties

Micha Sharir, Noam Solomon

Let $P$ be a set of $m$ points and $L$ a set of $n$ lines in $R^{4}$ , such that the points of $P$ lie on an algebraic three-dimensional surface of degree $D$ that does not co…

cs.CG2016

Depth contours in arrangements of halfplanes

Sariel Har-Peled, Micha Sharir

Let $H$ be a set of $n$ halfplanes in $R^{2}$ in general position, and let $k < n$ be a given parameter. We show that the number of vertices of the arrangement of $H$ that lie…

cs.CG2016★ 3 cited

The Decision Tree Complexity for $k$ -SUM is at most Nearly Quadratic

Esther Ezra, Micha Sharir

Following a recent improvement of Cardinal et al. on the complexity of a linear decision tree for $k$ -SUM, resulting in $O (n^{3} lo g^{3} n)$ linear queries, we present a further impr…

cs.CG2016

Eliminating Depth Cycles among Triangles in Three Dimensions

Boris Aronov, Edward Y. Miller, Micha Sharir

Given $n$ pairwise openly disjoint triangles in 3-space, their vertical depth relation may contain cycles. We show that, for any $ε > 0$ , the triangles can be cut into $O(n…

Distinct distances between a collinear set and an arbitrary set of points

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances

Incidences between points and lines on two- and three-dimensional varieties

Depth contours in arrangements of halfplanes

The Decision Tree Complexity for k-SUM is at most Nearly Quadratic

Eliminating Depth Cycles among Triangles in Three Dimensions

The Decision Tree Complexity for $k$ -SUM is at most Nearly Quadratic