Esther Ezra

SODA Conference 2024 Conference Paper

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 ℝ d into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open problems involving the vertical decomposition of substructures of arrangements for d = 3, 4: (i) Let S be a collection of n semi-algebraic sets of constant complexity in ℝ 3, and let U ( m ) be an upper bound on the complexity of the union U ( S ‘) of any subset S’ ⊆ S of size at most m. We prove that the complexity of the vertical decomposition of the complement of U ( S ) is O * ( n 2 + U ( n )) (where the O * (·) notation hides subpolynomial factors). We also show that the complexity of the vertical decomposition of the entire arrangement A ( S ) is O*(n 2 + X ), where X is the number of vertices in A ( S ). (ii) Let F be a collection of n trivariate functions whose graphs are semi-algebraic sets of constant complexity. We show that the complexity of the vertical decomposition of the portion of the arrangement A ( F ) in ℝ 4 lying below the lower envelope of F is O *( n 3 ). These results lead to efficient algorithms for a variety of problems involving these decompositions, including algorithms for constructing the decompositions themselves, and for constructing (1/ r )-cuttings of substructures of arrangements of the kinds considered above. One additional algorithm of interest is for output-sensitive point enclosure queries amid semi-algebraic sets in three or four dimensions. In addition, as a main domain of applications, we study various proximity problems involving points and lines in ℝ 3: We first present a linear-size data structure for answering nearest-neighbor queries, with points, amid n lines in ℝ 3 in O *( n 2/3 ) time per query. We also study the converse problem, where we return the nearest neighbor of a query line amid n input points, or lines, in ℝ 3. We obtain a data structure of O *( n 4 ) size that answers a nearest-neighbor query in O (log n ) time. * Work by Pankaj Agarwal has been partially supported by NSF grants IIS-18-14493, CCF-20-07556, and CCF-22-23870. Work by Esther Ezra has been partially supported by Israel Science Foundation Grant 800/22, and also by US-Israel Binational Science Foundation under Grant 2022131. Work by Micha Sharir has been partially supported by Israel Science Foundation Grant 260/18.

SODA Conference 2019 Conference Paper

Constructive Polynomial Partitioning for Algebraic Curves in R 3 with Applications

• Boris Aronov
• Esther Ezra
• Joshua Zahl

In 2015, Guth proved that, for any set of k -dimensional varieties in ℝ 3 and for any positive integer D, there exists a polynomial of degree at most D whose zero-set divides ℝ 3 into open connected “cells, ” so that only a small fraction of the given varieties intersect each cell. 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 curves (or even lines) in ℝ 3. We present an efficient algorithmic construction for this setting. Given a set of n input 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 at most O ( n / D 2 ) curves from the input. The construction time is O ( n 2 ), where the constant of proportionality depends on D and the maximum degree of the polynomials defining the input curves. For the case of lines in 3-space we present an improved implementation, whose running time is O ( n 4/3 polylog n ). As an application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently studied by Aronov et al. (2017) and De Berg (2017). Our main result is an algorithm that cuts n triangles 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 nearly worst-case optimal. We also sketch several other applications of our effective partitioning for curves in ℝ 3.

SODA Conference 2014 Conference Paper

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

• Esther Ezra

JMLR Journal 2014 Journal Article

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 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 applications of interest are: Learning to rank from pairwise preferences, and clustering with side information (a.k.a. semi-supervised clustering). The tool we use is based on the learner's ability to compute an estimator of the difference between the loss of any hypothesis and some fixed “pivotal” hypothesis to within an absolute error of at most $\epsilon$ times the disagreement measure ($\ell_1$ distance) between the two hypotheses. We prove that such an estimator implies the existence of a learning algorithm which, at each iteration, reduces its in-class excess risk to within a constant factor. Each iteration replaces the current pivotal hypothesis with the minimizer of the estimated loss difference function with respect to the previous pivotal hypothesis. The label complexity essentially becomes that of computing this estimator. [abs] [ pdf ][ bib ] &copy JMLR 2014. ( edit, beta )

SODA Conference 2011 Conference Paper

Improved Bound for the Union of Fat Triangles

• Esther Ezra
• Boris Aronov
• Micha Sharir

STOC Conference 2009 Conference Paper

Small-size epsilon-nets for axis-parallel rectangles and boxes

• Boris Aronov
• Esther Ezra
• Micha Sharir

We show the existence of ε-nets of size O(1/ε log log 1/ε) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in reals 3 and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size

FOCS Conference 2008 Conference Paper

On the Union of Cylinders in Three Dimensions

• Esther Ezra

We show that the combinatorial complexity of the union of n infinite cylinders in R 3, having arbitrary radii, is O(n 2+epsiv ), for any epsiv >0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir, who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir, in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in. Finally, we extend our technique to the case of "cigars'' of arbitrary radii (that is, Minkowski sums of line-segments and balls), and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in for the restricted case where all cigars are (nearly) equal-radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders, and is significantly simpler than the proof presented in [3].

FOCS Conference 2007 Conference Paper

Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions

• Esther Ezra
• Micha Sharir

We show that the combinatorial complexity of the. union of n "fat" tetrahedra in 3-space (i. e. , tetrahedra all of whose solid angles are at least. some fixed constant) of arbitrary sizes, is O(n 2+epsiv ), for any epsiv > 0: the bound is almost tight in the worst case, thus almost settling a conjecture of Pach el al. [24]. Our result extends, in a significant way, the result of Pach et al. [24] for the restricted case of nearly congruent cubes. The analysis uses cuttings, combined with the Dobkin-K'irkpatrick hierarchical decomposition of convex polytopes, in order to partition space into subcells, so that, on average, the overwhelming majority of the tetrahedra intersecting a subcell Delta behave as fat dihedral wedges in Delta. As an immediate corollary, we obtain that the combinatorial complexity of the union of n cubes in R 3 having arbitrary side lengths, is O(n 2+epsiv ), for any epsiv > 0 again, significantly extending the result of [24]. Our analysis can easily he extended to yield a nearly-quadratic bound on the complexity of the union of arbitrarily oriented fat triangular prisms (whose cross-sections have, arbitrary sizes) in R 3. Finally, we show that a simple variant of our analysis implies a nearly-linear bound on the complexity of the union of fat triangles in the plane.

SODA Conference 2004 Conference Paper

Output-sensitive construction of the union of triangles

• Esther Ezra
• Micha Sharir