7 papers
Subquadratic Algorithms for Some \textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model
Boris Aronov, Mark de Berg, Jean Cardinal +3
We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Gi…
On Ray Shooting for Triangles in 3-Space and Related Problems
Esther Ezra, Micha Sharir
We consider several problems that involve lines in three dimensions, and present improved algorithms for solving them. The problems include (i) ray shooting amid triangles in …
On rich lenses in planar arrangements of circles and related problems
Esther Ezra, Orit E. Raz, Micha Sharir +1
We show that the maximum number of pairwise non-overlapping -rich lenses (lenses formed by at least circles) in an arrangement of circles in the plane is $O\left(\frac{n…
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems
Boris Aronov, Esther Ezra, Micha Sharir
We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets $…
On Pseudo-disk Hypergraphs
Boris Aronov, Anirudh Donakonda, Esther Ezra +1
Let be a family of pseudo-disks in the plane, and be a finite subset of . Consider the hypergraph whose vertices are the pseudo-disks in and the edges are a…
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
Esther Ezra, Sariel Har-Peled, Haim Kaplan +1
We re-examine parameters for the two main space decomposition techniques---bottom-vertex triangulation, and vertical decomposition, including their…