16 citations · 51 across the 14 of their papers we have counts for
21 papers
Point and Line Nearest-Neighbor Searching in 3-Space
Pankaj K. Agarwal, Esther Ezra, Micha Sharir
This paper presents data structures for nearest-neighbor (NN) searching problems involving points, lines, segments, and triangles in 3-space, achieving significantly better perform…
Nearly-Tight Bounds for Vertical Decomposition in Three and Four Dimensions
Pankaj K. Agarwal, Esther Ezra, Micha Sharir
Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in into constant-complexity subcells. In…
Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane
Pankaj K. Agarwal, Esther Ezra, Micha Sharir
Let be a set of points in , let be a set of semi-algebraic sets of constant complexity in , let be a semigroup, and let $w: P…
Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D
Pankaj K. Agarwal, Esther Ezra, Micha Sharir
Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in -space into constant-complexity subcells. In this p…
Intersection Searching amid Tetrahedra in Four Dimensions
Esther Ezra, Micha Sharir
We develop data structures for intersection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study three main problems: (i) Preprocess a…
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
Pankaj K. Agarwal, Boris Aronov, Esther Ezra +2
Let be a set of flat (planar) semi-algebraic regions in of constant complexity (e.g., triangles, disks), which we call plates. We wish to preproces…
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 $…
Constructive Polynomial Partitioning for Algebraic Curves in with Applications
Boris Aronov, Esther Ezra, Joshua Zahl
In 2015, Guth proved that for any set of -dimensional bounded complexity varieties in and for any positive integer , there exists a polynomial of degree at mos…
An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Pankaj K. Agarwal, Boris Aronov, Esther Ezra +1
In 2015, Guth proved that if is a collection of -dimensional semi-algebraic sets in and if is an integer, then there is a -variate polynomial…
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…
The Decision Tree Complexity for -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 -SUM, resulting in linear queries, we present a further impr…
On the Beck-Fiala Conjecture for Random Set Systems
Esther Ezra, Shachar Lovett
Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems , where each element lies in $…
Shallow Packings in Geometry
Esther Ezra
We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let $\V$ be a finite set system defined over an -point…
A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
Esther Ezra
Let be a set system on an -point set . The \emph{discrepancy} of is defined as the minimum of the largest deviation from an even split, over all subsets of $S \in…
Small-Size Relative (p,Epsilon)-Approximations for Well-Behaved Range Spaces
Esther Ezra
We present improved upper bounds for the size of relative (p,Epsilon)-approximation for range spaces with the following property: For any (finite) range space projected onto (that…
Active Learning Using Smooth Relative Regret Approximations with Applications
Nir Ailon, Ron Begleiter, Esther Ezra
The disagreement coefficient of Hanneke has become a central data independent invariant in proving active learning rates. It has been shown in various ways that a concept class wit…
Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing
Esther Ezra, Wolfgang Mulzer
Motivated by the desire to cope with data imprecision, we study methods for taking advantage of preliminary information about point sets in order to speed up the computation of cer…