158 citations · 543 across the 80 of their papers we have counts for
5 papers · 2 filters
Relative -Approximations in Geometry
Sariel Har-Peled, Micha Sharir
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-dime…
Semi-algebraic Range Reporting and Emptiness Searching with Applications
Micha Sharir, Hayim Shaul
In a typical range emptiness searching (resp., reporting) problem, we are given a set of points in , and wish to preprocess it into a data structure that supports…
Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space
Ophir Setter
We present a general framework for computing two-dimensional Voronoi diagrams of different classes of sites under various distance functions. The framework is sufficiently general…
On lines and Joints
Haim Kaplan, Micha Sharir, Eugenii Shustin
Let be a set of lines in , for . A {\em joint} of is a point incident to at least lines of , not all in a common hyperplane. Using a very simpl…
On Lines, Joints, and Incidences in Three Dimensions
György Elekes, Haim Kaplan, Micha Sharir
We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz \cite{GK}, to obtain several sharp bounds on the number of incidences between lines and points in t…