Linear Data Structures for Fast Ray-Shooting amidst Convex (2009)
Haim Kaplan, Natan Rubin, Micha Sharir
We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them into a data...
Line Transversals of Convex Polyhedra in $\reals^3$ (2008)
Kaplan, Haim, Rubin, Natan, Sharir, Micha
We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the combinatorial complexity of the set $\T$ of line transversals of a collection $\P$ of $k$ convex polyhedra in $\reals^3$ with a...
Haim Kaplan, Natan Rubin, Micha Sharir
Abstract. We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them...
Abstract Counting Colors in Boxes ∗ (2008)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Line Transversals of Convex Polyhedra in R 3∗ (2008)
Haim Kaplan, Natan Rubin, Micha Sharir
We establish a bound of O(n 2 k 1+ε), for any ε> 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in R 3 with a total of n facets, and...
Counting colors in boxes (2007)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Counting colors in boxes (2007)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Elad Verbin, Curriculum Vitæ, Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin, ...
received best paper award in Combinatorial Pattern Matching (CPM) 2006. To be published in Theoretical Computer Science, special issue on The Burrows-Wheeler Transform and its Applications (expected...