Source author record

Esther Ezra

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Discrete Mathematics Machine Learning math.CO

Catalog footprint

Research overview

11works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Intersection Searching amid Tetrahedra in Four Dimensions

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 set of $n$ tetrahedra in $\reals^4$ into a data structure for answering segment-intersection queries amid the given tetrahedra (referred to as \emph{segment-tetrahedron intersection queries}). (ii) Preprocess a set of $n$ triangles in $\reals^4$ into a data structure that supports triangle-intersection queries amid the input triangles (referred to as \emph{triangle-triangle intersection queries}). (iii) Preprocess a set of $n$ segments in $\reals^4$ into a data structure that supports tetrahedron-intersection queries amid the input segments (referred to as \emph{tetrahedron-segment intersection queries}). In each problem we want either to detect an intersection, or to count or report all intersections. As far as we can tell, these problems have not been previously studied. For problem (i), we first present a "standard" solution which, for any prespecified value $n \le s \le n^6$ of a so-called storage parameter $s$ , yields a data structure with $O^*(s)$ storage and expected preprocessing, which answers an intersection query in $O^*(n/s^{1/6})$ time (here and in what follows, the $O^*(\cdot)$ notation hides subpolynomial factors). For problems (ii) and (iii), using similar arguments, we present a solution that has the same asymptotic performance bounds. We then improve the solution for problem (i), and present a more intricate data structure that uses $O^*(n^{2})$ storage and expected preprocessing, and answers a segment-tetrahedron intersection query in $O^*(n^{1/2})$ time.

preprint2021arXiv

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

In 2015, Guth proved that if $S$ is a collection of $n$ $g$ -dimensional semi-algebraic sets in $\mathbb{R}^d$ and if $D\geq 1$ is an integer, then there is a $d$ -variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $S$ . Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently -- the expected running time of our algorithm is linear in $|S|$ . Our approach exploits the technique of quantifier elimination combined with that of $ε$ -samples. We also present an extension of our construction to multi-level polynomial partitioning for semi-algebraic sets in $\mathbb{R}^d$ . We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+ε})$ . The second is a data structure for answering range-searching queries with semi-algebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+ε})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+ε})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudo-segments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$ , where we show a nearly-optimal algorithm to cut $n$ pairwise disjoint non-vertical triangles in $\mathbb{R}^3$ into pieces that form a depth order.

preprint2021arXiv

On Ray Shooting for Triangles in 3-Space and Related Problems

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 $R^3$ , (ii) reporting intersections between query lines (segments, or rays) and input triangles, as well as approximately counting the number of such intersections, (iii) computing the intersection of two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections in a set of lines in $R^3$ , and (v) output-sensitive construction of an arrangement of triangles in three dimensions. Our approach is based on the polynomial partitioning technique. For example, our ray-shooting algorithm processes a set of $n$ triangles in $R^3$ into a data structure for answering ray shooting queries amid the given triangles, which uses $O(n^{3/2+\varepsilon})$ storage and preprocessing, and answers a query in $O(n^{1/2+\varepsilon})$ time, for any $\varepsilon>0$ . This is a significant improvement over known results, obtained more than 25 years ago, in which, with this amount of storage, the query time bound is roughly $n^{5/8}$ . The algorithms for the other problems have similar performance bounds, with similar improvements over previous results. We also derive a nontrivial improved tradeoff between storage and query time. Using it, we obtain algorithms that answer $m$ queries on $n$ objects in $\max \left\{ O(m^{2/3}n^{5/6+\varepsilon} + n^{1+\varepsilon}),\; O(m^{5/6+\varepsilon}n^{2/3} + m^{1+\varepsilon}) \right\}$ time, for any $\varepsilon>0$ , again an improvement over the earlier bounds.

preprint2020arXiv

Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications

In 2015, Guth proved that for any set of $k$ -dimensional bounded complexity varieties in $\mathbb{R}^d$ and for any positive integer $D$ , there exists a polynomial of degree at most $D$ whose zero set divides $\mathbb{R}^d$ into open connected sets, so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for $k>0$ , it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in $\mathbb{R}^3$ . We present an efficient algorithmic construction for this setting. Given a set of $n$ input algebraic curves and a positive integer $D$ , we efficiently construct a decomposition of space into $O(D^3\log^3{D})$ open "cells," each of which meets $O(n/D^2)$ curves from the input. The construction time is $O(n^2)$ . For the case of lines in $3$ -space we present an improved implementation, whose running time is $O(n^{4/3} \log^{O(1)} n)$ . The constant of proportionality in both time bounds depends on $D$ and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among non-vertical lines in $3$ -space, recently studied by Aronov and Sharir (2018), and show an algorithm that cuts $n$ such lines into $O(n^{3/2+ε})$ pieces that are depth-cycle free, for any $ε> 0$ . The algorithm runs in $O(n^{3/2+ε})$ time, which is a considerable improvement over the previously known algorithms.

preprint2016arXiv

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

Following a recent improvement of Cardinal et al. on the complexity of a linear decision tree for $k$ -SUM, resulting in $O(n^3 \log^3{n})$ linear queries, we present a further improvement to $O(n^2 \log^2{n})$ such queries.

preprint2015arXiv

On the Beck-Fiala Conjecture for Random Set Systems

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,Σ)$ , where each element $x \in X$ lies in $t$ randomly selected sets of $Σ$ , where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We show that when $|Σ| \ge |X|$ the hereditary discrepancy of $(X,Σ)$ is with high probability $O(\sqrt{t \log t})$ ; and when $|X| \gg |Σ|^t$ the hereditary discrepancy of $(X,Σ)$ is with high probability $O(1)$ . The first bound combines the Lov{á}sz Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.

preprint2014arXiv

Shallow Packings in Geometry

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 $n$ -point set $X$ ; we view $\V$ as a set of indicator vectors over the $n$ -dimensional unit cube. A $δ$ -separated set of $\V$ is a subcollection $\W$, s.t. the Hamming distance between each pair $\uu, \vv \in \W$ is greater than $δ$ , where $δ> 0$ is an integer parameter. The $δ$ -packing number is then defined as the cardinality of the largest $δ$ -separated subcollection of $\V$. Haussler showed an asymptotically tight bound of $Θ((n/δ)^d)$ on the $δ$ -packing number if $\V$ has VC-dimension (or \emph{primal shatter dimension}) $d$ . We refine this bound for the scenario where, for any subset, $X' \subseteq X$ of size $m \le n$ and for any parameter $1 \le k \le m$ , the number of vectors of length at most $k$ in the restriction of $\V$ to $X'$ is only $O(m^{d_1} k^{d-d_1})$ , for a fixed integer $d > 0$ and a real parameter $1 \le d_1 \le d$ (this generalizes the standard notion of \emph{bounded primal shatter dimension} when $d_1 = d$ ). In this case when $\V$ is " $k$ -shallow" (all vector lengths are at most $k$ ), we show that its $δ$ -packing number is $O(n^{d_1} k^{d-d_1}/δ^d)$ , matching Haussler's bound for the special cases where $d_1=d$ or $k=n$ . As an immediate consequence we conclude that set systems of halfspaces, balls, and parallel slabs defined over $n$ points in $d$ -space admit better packing numbers when $k$ is smaller than $n$ . Last but not least, we describe applications to (i) spanning trees of low total crossing number, and (ii) geometric discrepancy, based on previous work by the author.

preprint2013arXiv

A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

Let $(X,§)$ be a set system on an $n$ -point set $X$ . The \emph{discrepancy} of $§$ is defined as the minimum of the largest deviation from an even split, over all subsets of $S \in §$ and two-colorings $χ$ on $X$ . We consider the scenario where, for any subset $X' \subseteq X$ of size $m \le n$ and for any parameter $1 \le k \le m$ , the number of restrictions of the sets of $§$ to $X'$ of size at most $k$ is only $O(m^{d_1} k^{d-d_1})$ , for fixed integers $d > 0$ and $1 \le d_1 \le d$ (this generalizes the standard notion of \emph{bounded primal shatter dimension} when $d_1 = d$ ). In this case we show that there exists a coloring $χ$ with discrepancy bound $O^{*}(|S|^{1/2 - d_1/(2d)} n^{(d_1 - 1)/(2d)})$ , for each $S \in §$ , where $O^{*}(\cdot)$ hides a polylogarithmic factor in $n$ . This bound is tight up to a polylogarithmic factor \cite{Mat-95, Mat-99} and the corresponding coloring $χ$ can be computed in expected polynomial time using the very recent machinery of Lovett and Meka for constructive discrepancy minimization \cite{LM-12}. Our bound improves and generalizes the bounds obtained from the machinery of Har-Peled and Sharir \cite{HS-11} (and the follow-up work in \cite{SZ-12}) for points and halfspaces in $d$ -space for $d \ge 3$ .

preprint2012arXiv

Active Learning Using Smooth Relative Regret Approximations with Applications

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 with low complexity together with a bound on the disagreement coefficient at an optimal solution allows active learning rates that are superior to passive learning ones. We present a different tool for pool based active learning which follows from the existence of a certain uniform version of low disagreement coefficient, but is not equivalent to it. In fact, we present two fundamental active learning problems of significant interest for which our approach allows nontrivial active learning bounds. However, any general purpose method relying on the disagreement coefficient bounds only fails to guarantee any useful bounds for these problems. The tool we use is based on the learner's ability to compute an estimator of the difference between the loss of any hypotheses and some fixed "pivotal" hypothesis to within an absolute error of at most $\eps$ times the

preprint2012arXiv

Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing

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 certain structures associated with them. In particular, we study the following problem: given a set L of n lines in the plane, we wish to preprocess L such that later, upon receiving a set P of n points, each of which lies on a distinct line of L, we can construct the convex hull of P efficiently. We show that in quadratic time and space it is possible to construct a data structure on L that enables us to compute the convex hull of any such point set P in O(n alpha(n) log* n) expected time. If we further assume that the points are "oblivious" with respect to the data structure, the running time improves to O(n alpha(n)). The analysis applies almost verbatim when L is a set of line-segments, and yields similar asymptotic bounds. We present several extensions, including a trade-off between space and query time and an output-sensitive algorithm. We also study the "dual problem" where we show how to efficiently compute the (<= k)-level of n lines in the plane, each of which lies on a distinct point (given in advance). We complement our results by Omega(n log n) lower bounds under the algebraic computation tree model for several related problems, including sorting a set of points (according to, say, their x-order), each of which lies on a given line known in advance. Therefore, the convex hull problem under our setting is easier than sorting, contrary to the "standard" convex hull and sorting problems, in which the two problems require Theta(n log n) steps in the worst case (under the algebraic computation tree model).

preprint2012arXiv

Small-Size Relative (p,Epsilon)-Approximations for Well-Behaved Range Spaces

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 is, restricted to) a ground set of size n and for any parameter 1 <= k <= n, the number of ranges of size at most k is only nearly-linear in n and polynomial in k. Such range spaces are called "well behaved". Our bound is an improvement over the bound O(\log{(1/p)/\eps^2 p) introduced by Li etal. for the general case (where this bound has been shown to be tight in the worst case), when p << Epsilon. We also show that such small size relative (p,Epsilon)-approximations can be constructed in expected polynomial time. Our bound also has an interesting interpretation in the context of "p-nets": As observed by Har-Peled and Sharir, p-nets are special cases of relative (p,Epsilon)-approximations. Specifically, when Epsilon is a constant smaller than 1, their analysis implies that there are p-nets of size O(\log{(1/p)}/p) that are \emph{also} relative approximations. In this context our construction significantly improves this bound for well-behaved range spaces. Despite the progress in the theory of p-nets and the existence of improved bounds corresponding to the cases that we study, these bounds do not necessarily guarantee a bounded relative error. Lastly, we present several geometric scenarios of well-behaved range spaces, and show the resulting bound for each of these cases obtained as a consequence of our analysis. In particular, when Epsilon is a constant smaller than 1, our bound for points and axis-parallel boxes in two and three dimensions, as well as points and "fat" triangles in the plane, matches the optimal bound for p-nets.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Esther Ezra

Research overview

Is this your work?

11 publications

Intersection Searching amid Tetrahedra in Four Dimensions

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

On Ray Shooting for Triangles in 3-Space and Related Problems

Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications

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

On the Beck-Fiala Conjecture for Random Set Systems

Shallow Packings in Geometry

A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

Active Learning Using Smooth Relative Regret Approximations with Applications

Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing

Small-Size Relative (p,Epsilon)-Approximations for Well-Behaved Range Spaces

See the researcher in context

Building this map preview

Esther Ezra

Research overview

Is this your work?

11 publications

Intersection Searching amid Tetrahedra in Four Dimensions

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

On Ray Shooting for Triangles in 3-Space and Related Problems

Constructive Polynomial Partitioning for Algebraic Curves in R3\mathbb{R}^3R3 with Applications

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

On the Beck-Fiala Conjecture for Random Set Systems

Shallow Packings in Geometry

A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

Active Learning Using Smooth Relative Regret Approximations with Applications

Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing

Small-Size Relative (p,Epsilon)-Approximations for Well-Behaved Range Spaces

See the researcher in context

Building this map preview

Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications

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