23 Search Results for "Ezra, Esther"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.45
BFS and Reverse Shortest Paths for Ball Intersection Graphs in Three and Higher Dimensions

Authors: Matthew J. Katz, Rachel Saban, and Micha Sharir

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let ℬ be a collection of n arbitrary balls in ℝ³, and let G₀(ℬ) be their intersection graph. We provide an algorithm for performing BFS on G₀(ℬ), which runs in O^*(n^{4/3}) time, where the O^*(⋅) notation hides subpolynomial factors. For r ≥ 0, let G_r(ℬ) be the intersection graph of the set ℬ_r = {B+r ∣ B ∈ ℬ}, where B+r is the ball concentric with B whose radius is larger by r than the radius of B. We provide an efficient algorithm for the reverse shortest path (RSP) problem, where we are given two designated balls B_s, B_t of ℬ and a parameter 0 < λ < n, and seek the smallest value r^* for which G_{r^*}(ℬ) contains a path from B_s to B_t of at most λ edges. For the special case of congruent balls (equivalently, for points in ℝ³), the algorithm runs in O^*(n^{29/21}) ≈ O^*(n^{1.381}) time. For the general case, the algorithm runs in O^*(n^{56/39}) ≈ O^*(n^{1.436}) time. We also extend the technique to handle other measures of expansion and higher dimensions.
Cite as

Matthew J. Katz, Rachel Saban, and Micha Sharir. BFS and Reverse Shortest Paths for Ball Intersection Graphs in Three and Higher Dimensions. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{katz_et_al:LIPIcs.ISAAC.2025.45,
  author =	{Katz, Matthew J. and Saban, Rachel and Sharir, Micha},
  title =	{{BFS and Reverse Shortest Paths for Ball Intersection Graphs in Three and Higher Dimensions}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.45},
  URN =		{urn:nbn:de:0030-drops-249535},
  doi =		{10.4230/LIPIcs.ISAAC.2025.45},
  annote =	{Keywords: Computational geometry, reverse shortest paths, breadth-first search, shrink-and-bifurcate, intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.30
Incidences Between Curves and Points on the Grid

Authors: Esther Ezra and Micha Sharir

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We derive an improved upper bound for the number of incidences between the n vertices of a uniform grid and m convex or concave curves, each pair of which intersect in at most s points, for some integer parameter s ≥ 1. For a square grid, our bound is O(n^{2/3}m^{2/3} + m^{1-1/(3s)} n^{(s+1)/3s} + m + n) . This improves a general bound of O(m n^{1/3}) on the number of incidences with respect to vertices of a grid and convex or concave curves. For a rectangular grid, which fits inside a 1×K rectangle, for some integer K > 1 (which generally may depend on n), the bound also depends on how large K is. The precise result is stated in Theorem 2, but, roughly, we get the same bound as above when K is not too large. Our analysis competes with a celebrated result of Bombieri and Pila [E. Bombieri and J. Pila, 1989], which gives (usually) a sharper bound if we assume that the input curves are algebraic of constant degree and the input points are vertices of the square grid. However, the analysis in [E. Bombieri and J. Pila, 1989] strongly relies on these assumptions, and cannot be extended to handle the more general setup considered here. As a main application, of independent interest, we present a variant of our technique for semi-algebraic range reporting on sets of points of "bounded spread" in the plane.
Cite as

Esther Ezra and Micha Sharir. Incidences Between Curves and Points on the Grid. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.ISAAC.2025.30,
  author =	{Ezra, Esther and Sharir, Micha},
  title =	{{Incidences Between Curves and Points on the Grid}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.30},
  URN =		{urn:nbn:de:0030-drops-249387},
  doi =		{10.4230/LIPIcs.ISAAC.2025.30},
  annote =	{Keywords: Geometric incidences, uniform grid, bounded spread, Pick’s theorem, range searching}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.25
Instance-Optimal Imprecise Convex Hull

Authors: Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Imprecise measurements of a point set P = (p₁, …, p_n) can be modelled by a family of regions F = (R₁, …, R_n), where each imprecise region R_i ∈ F contains a unique point p_i ∈ P. A retrieval models an accurate measurement by replacing an imprecise region R_i with its corresponding point p_i. We construct the convex hull of an imprecise point set in the plane, by determining the cyclic ordering of the convex hull vertices of P as efficiently as possible. Efficiency is interpreted in two ways: (i) minimising the number of retrievals, and (ii) the computation time to determine the set of regions that must be retrieved. Previous works focused on only one of these two aspects: either minimising retrievals or optimising algorithmic runtime. Our contribution is the first to simultaneously achieve both. Let r(F, P) denote the minimal number of retrievals required by any algorithm to determine the convex hull of P for a given instance (F, P). For a family F of n constant-complexity polygons, our main result is a reconstruction algorithm that performs Θ(r(F, P)) retrievals in O(r(F, P) log³ n) time. Compared to previous approaches that achieve optimal retrieval counts, we improve the runtime per retrieval from polynomial to polylogarithmic. We extend the generality of previous results to simple k-gons, to pairwise disjoint disks with radii in [1,k], and to unit disks where at most k disks overlap in a single point. Our runtime scales linearly with k.
Cite as

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong. Instance-Optimal Imprecise Convex Hull. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2025.25,
  author =	{de Berg, Sarita and van der Hoog, Ivor and Rotenberg, Eva and Rutschmann, Daniel and Wong, Sampson},
  title =	{{Instance-Optimal Imprecise Convex Hull}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.25},
  URN =		{urn:nbn:de:0030-drops-244932},
  doi =		{10.4230/LIPIcs.ESA.2025.25},
  annote =	{Keywords: convex hull, imprecise geometry preprocessing model, partial information}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.67
Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.
Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.81
An O(nlog n) Algorithm for Single-Source Shortest Paths in Disk Graphs

Authors: Mark de Berg and Sergio Cabello

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We prove that the single-source shortest-path problem on disk graphs can be solved in O(n log n) expected time, and that it can be solved on intersection graphs of fat triangles in O(n log³ n) time.
Cite as

Mark de Berg and Sergio Cabello. An O(nlog n) Algorithm for Single-Source Shortest Paths in Disk Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2025.81,
  author =	{de Berg, Mark and Cabello, Sergio},
  title =	{{An O(nlog n) Algorithm for Single-Source Shortest Paths in Disk Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{81:1--81:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.81},
  URN =		{urn:nbn:de:0030-drops-245494},
  doi =		{10.4230/LIPIcs.ESA.2025.81},
  annote =	{Keywords: shortest path, geometric intersection graph, disk graph, fat triangles}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.2
Covering Simple Orthogonal Polygons with Rectangles

Authors: Aniket Basu Roy

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study the problem of Covering Orthogonal Polygons with Rectangles, focusing on three variants: covering the interior, the boundary, and the corners. While previous work provided constant-factor approximation algorithms for these problems, significant improvements had not been achieved for over two decades. The main contribution of this work is the development of a Polynomial Time Approximation Scheme (PTAS) for both the Boundary Cover and Corner Cover problems on simple polygons, using a local search algorithm. Our work advances the state of the art, improving upon the previous best-known 4-approximation for the Boundary Cover and 2-approximation for the Corner Cover problems. The technical core of our work lies in proving the existence of planar support graphs for certain geometric hypergraphs defined by the polygon and its containment-maximal rectangles. This structural insight enables the application of the local search framework to achieve the PTAS results. We also demonstrate the limitations of this approach by constructing instances where local search fails for the Interior Cover and certain dual problems, such as the Maximum Antirectangle and Hitting Set problems. Additionally, the methods yield a PTAS for a special case of the Discrete Independent Set problem for rectangles. These results not only settle longstanding open questions but also introduce new techniques that may be of independent interest within computational geometry.
Cite as

Aniket Basu Roy. Covering Simple Orthogonal Polygons with Rectangles. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{basuroy:LIPIcs.APPROX/RANDOM.2025.2,
  author =	{Basu Roy, Aniket},
  title =	{{Covering Simple Orthogonal Polygons with Rectangles}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.2},
  URN =		{urn:nbn:de:0030-drops-243686},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.2},
  annote =	{Keywords: Polygon Covering, Approximation Algorithms, Orthogonal Polygons, Rectangles, Local Search, Planar Supports}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.17
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

Authors: Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}).
Cite as

Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth. Sparse Bounded Hop-Spanners for Geometric Intersection Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2025.17,
  author =	{Bhore, Sujoy and Chan, Timothy M. and Huang, Zhengcheng and Smorodinsky, Shakhar and T\'{o}th, Csaba D.},
  title =	{{Sparse Bounded Hop-Spanners for Geometric Intersection Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.17},
  URN =		{urn:nbn:de:0030-drops-231698},
  doi =		{10.4230/LIPIcs.SoCG.2025.17},
  annote =	{Keywords: Geometric Spanners, Geometric Intersection Graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.73
Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position

Authors: Anastasiia Tkachenko and Haitao Wang

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Given a set P of n points in the plane, its unit-disk graph G(P) is a graph with P as its vertex set such that two points of P are connected by an edge if their (Euclidean) distance is at most 1. We consider several classical problems on G(P) in a special setting when points of P are in convex position. These problems are all NP-hard in the general case. We present efficient algorithms for these problems under the convex position assumption. ● For the problem of finding the smallest dominating set of G(P), we present an O(knlog n) time algorithm, where k is the smallest dominating set size. We also consider the weighted case in which each point of P has a weight and the goal is to find a dominating set in G(P) with minimum total weight; our algorithm runs in O(n³log² n) time. In particular, for a given k, our algorithm can compute in O(kn²log² n) time a minimum weight dominating set of size at most k (if it exists). ● For the discrete k-center problem, which is to find a subset of k points in P (called centers) for a given k, such that the maximum distance between any point in P and its nearest center is minimized. We present an algorithm that solves the problem in O(min{n^{4/3}log n+knlog² n,k² nlog²n}) time, which is O(n²log² n) in the worst case when k = Θ(n). For comparison, the runtime of the current best algorithm for the continuous version of the problem where centers can be anywhere in the plane is O(n³ log n). ● For the problem of finding a maximum independent set in G(P), we give an algorithm of O(n^{7/2}) time and another randomized algorithm of O(n^{37/11}) expected time, which improve the previous best result of O(n⁶log n) time. Our algorithms can be extended to compute a maximum-weight independent set in G(P) with the same time complexities when points of P have weights. - If we are looking for an (unweighted) independent set of size 3, we derive an algorithm of O(nlog n) time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position). - If points of P have weights and are not necessarily in convex position, we present an algorithm that can find a maximum-weight independent set of size 3 in O(n^{5/3+δ}) time for an arbitrarily small constant δ > 0. By slightly modifying the algorithm, a maximum-weight clique of size 3 can also be found within the same time complexity. ● For the dispersion problem, which is to find a subset of k points from P for a given k, such that the minimum pairwise distance of the points in the subset is maximized. We present an algorithm of O(n^{7/2}log n) time and another randomized algorithm of O(n^{37/11}log n) expected time, which improve the previous best result of O(n⁶) time. - If k = 3, we present an algorithm of O(nlog² n) time and another randomized algorithm of O(nlog n) expected time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position).
Cite as

Anastasiia Tkachenko and Haitao Wang. Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tkachenko_et_al:LIPIcs.STACS.2025.73,
  author =	{Tkachenko, Anastasiia and Wang, Haitao},
  title =	{{Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.73},
  URN =		{urn:nbn:de:0030-drops-228982},
  doi =		{10.4230/LIPIcs.STACS.2025.73},
  annote =	{Keywords: Dominating set, k-center, geometric set cover, independent set, clique, vertex cover, unit-disk graphs, convex position, dispersion, maximally separated sets}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.6
Lower Envelopes of Surface Patches in 3-Space

Authors: Pankaj K. Agarwal, Esther Ezra, and Micha Sharir

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Let Σ be a collection of n surface patches, each being the graph of a partially defined semi-algebraic function of constant description complexity, and assume that any triple of them intersect in at most s = 2 points. We show that the complexity of the lower envelope of the surfaces in Σ is O(n² log^{6+ε} n), for any ε > 0. This almost settles a long-standing open problem posed by Halperin and Sharir, thirty years ago, who showed the nearly-optimal albeit weaker bound of O(n²⋅ 2^{c√{log n}}) on the complexity of the lower envelope, where c > 0 is some constant. Our approach is fairly simple and is based on hierarchical cuttings and gradations, as well as a simple charging scheme. We extend our analysis to the case s > 2, under a "favorable cross section" assumption, in which case we show that the bound on the complexity of the lower envelope is O(n² log^{11+ε} n), for any ε > 0. Incorporating these bounds with the randomized incremental construction algorithms of Boissonnat and Dobrindt, we obtain efficient constructions of lower envelopes of surface patches with the above properties, whose overall expected running time is O(n² polylog), as well as efficient data structures that support point location queries in their minimization diagrams in O(log²n) expected time.
Cite as

Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Lower Envelopes of Surface Patches in 3-Space. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ESA.2024.6,
  author =	{Agarwal, Pankaj K. and Ezra, Esther and Sharir, Micha},
  title =	{{Lower Envelopes of Surface Patches in 3-Space}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.6},
  URN =		{urn:nbn:de:0030-drops-210772},
  doi =		{10.4230/LIPIcs.ESA.2024.6},
  annote =	{Keywords: Hierarchical cuttings, surface patches in 3-space, lower envelopes, charging scheme, gradation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.4
Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane

Authors: Pankaj K. Agarwal, Esther Ezra, and Micha Sharir

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Let P be a set of m points in ℝ², let Σ be a set of n semi-algebraic sets of constant complexity in ℝ², let (S,+) be a semigroup, and let w: P → S be a weight function on the points of P. We describe a randomized algorithm for computing w(P∩σ) for every σ ∈ Σ in overall expected time O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n), where s > 0 is a constant that bounds the maximum complexity of the regions of Σ, and where the O^*(⋅) notation hides subpolynomial factors. For s ≥ 3, surprisingly, this bound is smaller than the best-known bound for answering m such queries in an on-line manner. The latter takes O^*(m^{s/(2s-1)}n^{(2s-2)/(2s-1)} + m + n) time. Let Φ: Σ × P → {0,1} be the Boolean predicate (of constant complexity) such that Φ(σ,p) = 1 if p ∈ σ and 0 otherwise, and let Σ_Φ P = {(σ,p) ∈ Σ× P ∣ Φ(σ,p) = 1}. Our algorithm actually computes a partition ℬ_Φ of Σ_Φ P into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n). It is straightforward to compute w(P∩σ) for all σ ∈ Σ from ℬ_Φ. Similarly, if η: Σ → S is a weight function on the regions of Σ, ∑_{σ ∈ Σ: p ∈ σ} η(σ), for every point p ∈ P, can be computed from ℬ_Φ in a straightforward manner. We also mention a few other applications of computing ℬ_Φ.
Cite as

Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2024.4,
  author =	{Agarwal, Pankaj K. and Ezra, Esther and Sharir, Micha},
  title =	{{Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.4},
  URN =		{urn:nbn:de:0030-drops-199497},
  doi =		{10.4230/LIPIcs.SoCG.2024.4},
  annote =	{Keywords: Range-searching, semi-algebraic sets, pseudo-lines, duality, geometric cuttings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.3
Lower Bounds for Intersection Reporting Among Flat Objects

Authors: Peyman Afshani and Pingan Cheng

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Recently, Ezra and Sharir [Esther Ezra and Micha Sharir, 2022] showed an O(n^{3/2+σ}) space and O(n^{1/2+σ}) query time data structure for ray shooting among triangles in ℝ³. This improves the upper bound given by the classical S(n)Q(n)⁴ = O(n^{4+σ}) space-time tradeoff for the first time in almost 25 years and in fact lies on the tradeoff curve of S(n)Q(n)³ = O(n^{3+σ}). However, it seems difficult to apply their techniques beyond this specific space and time combination. This pheonomenon appears persistently in almost all recent advances of flat object intersection searching, e.g., line-tetrahedron intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], triangle-triangle intersection in ℝ⁴ [Esther Ezra and Micha Sharir, 2022], or even among flat semialgebraic objects [Agarwal et al., 2022]. We give a timely explanation to this phenomenon from a lower bound perspective. We prove that given a set 𝒮 of (d-1)-dimensional simplicies in ℝ^d, any data structure that can report all intersections with a query line in small (n^o(1)) query time must use Ω(n^{2(d-1)-o(1)}) space. This dashes the hope of any significant improvement to the tradeoff curves for small query time and almost matches the classical upper bound. We also obtain an almost matching space lower bound of Ω(n^{6-o(1)}) for triangle-triangle intersection reporting in ℝ⁴ when the query time is small. Along the way, we further develop the previous lower bound techniques by Afshani and Cheng [Afshani and Cheng, 2021; Afshani and Cheng, 2022].
Cite as

Peyman Afshani and Pingan Cheng. Lower Bounds for Intersection Reporting Among Flat Objects. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2023.3,
  author =	{Afshani, Peyman and Cheng, Pingan},
  title =	{{Lower Bounds for Intersection Reporting Among Flat Objects}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.3},
  URN =		{urn:nbn:de:0030-drops-178536},
  doi =		{10.4230/LIPIcs.SoCG.2023.3},
  annote =	{Keywords: Computational Geometry, Intersection Searching, Data Structure Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.5
Line Intersection Searching Amid Unit Balls in 3-Space

Authors: Pankaj K. Agarwal and Esther Ezra

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Let ℬ be a set of n unit balls in ℝ³. We present a linear-size data structure for storing ℬ that can determine in O^*(n^{1/2}) time whether a query line intersects any ball of ℬ and report all k such balls in additional O(k) time. The data structure can be constructed in O(n log n) time. (The O^*(⋅) notation hides subpolynomial factors, e.g., of the form O(n^ε), for arbitrarily small ε > 0, and their coefficients which depend on ε.) We also consider the dual problem: Let ℒ be a set of n lines in ℝ³. We preprocess ℒ, in O^*(n²) time, into a data structure of size O^*(n²) that can determine in O^*(1) time whether a query unit ball intersects any line of ℒ, or report all k such lines in additional O(k) time.
Cite as

Pankaj K. Agarwal and Esther Ezra. Line Intersection Searching Amid Unit Balls in 3-Space. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2023.5,
  author =	{Agarwal, Pankaj K. and Ezra, Esther},
  title =	{{Line Intersection Searching Amid Unit Balls in 3-Space}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.5},
  URN =		{urn:nbn:de:0030-drops-178559},
  doi =		{10.4230/LIPIcs.SoCG.2023.5},
  annote =	{Keywords: Intersection searching, cylindrical range searching, partition trees, union of cylinders}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.51
Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection

Authors: Esther Ezra and Micha Sharir

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We develop data structures for intersection detection queries in four dimensions that involve segments, triangles and tetrahedra. Specifically, we study two main problems: (i) Preprocess a set of n tetrahedra in {ℝ}⁴ into a data structure for answering segment-intersection queries amid the given tetrahedra (referred to as segment-tetrahedron intersection queries), and (ii) Preprocess a set of n triangles in {ℝ}⁴ into a data structure that supports triangle-intersection queries amid the input triangles (referred to as triangle-triangle intersection queries). 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 ≤ s ≤ n⁶ 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^*(⋅) notation hides subpolynomial factors). For problem (ii), 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²) storage and expected preprocessing, and answers a segment-tetrahedron intersection query in O^*(n^{1/2}) time. Using the parametric search technique of Agarwal and Matoušek [P. K. Agarwal and J. Matoušek, 1993], we can obtain data structures with similar performance bounds for the ray-shooting problem amid tetrahedra in {ℝ}⁴. Unfortunately, so far we do not know how to obtain a similar improvement for problem (ii). Our algorithms are based on a primal-dual technique for range searching with semi-algebraic sets, based on recent advances in this area [P. K. Agarwal et al., 2021; J. Matoušek and Z. Patáková, 2015]. As this is a result of independent interest, we spell out the details of this technique. As an application, we present a solution to the problem of "continuous collision detection" amid moving tetrahedra in 3-space. That is, the workspace consists of n tetrahedra, each moving at its own fixed velocity, and the goal is to detect a collision between some pair of moving tetrahedra. Using our solutions to problems (i) and (ii), we obtain an algorithm that detects a collision in O^*(n^{12/7}) expected time. We also present further applications, including an output-sensitive algorithm for constructing the arrangement of n tetrahedra in ℝ⁴ and an output-sensitive algorithm for constructing the intersection or union of two or several nonconvex polyhedra in ℝ⁴.
Cite as

Esther Ezra and Micha Sharir. Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ezra_et_al:LIPIcs.ESA.2022.51,
  author =	{Ezra, Esther and Sharir, Micha},
  title =	{{Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.51},
  URN =		{urn:nbn:de:0030-drops-169895},
  doi =		{10.4230/LIPIcs.ESA.2022.51},
  annote =	{Keywords: Computational geometry, Ray shooting, Tetrahedra in \{\mathbb{R}\}⁴, Intersection queries in \{\mathbb{R}\}⁴, Polynomial partitioning, Range searching, Semi-algebraic sets, Tradeoff}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.4
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

Authors: Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Let 𝒯 be a set of n planar semi-algebraic regions in ℝ³ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess 𝒯 into a data structure so that for a query object γ, which is also a plate, we can quickly answer various intersection queries, such as detecting whether γ intersects any plate of 𝒯, reporting all the plates intersected by γ, or counting them. We focus on two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in ℝ³ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in ℝ³. These interesting special cases form the building blocks for the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if 𝒯 is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^{4/3}) storage (where the O^*(⋅) notation hides subpolynomial factors) and answers an intersection query in O^*(n^{2/3}) time. Alternatively, by increasing the storage to O^*(n^{3/2}), the query time can be decreased to O^*(n^{ρ}), where ρ = (2t-3)/3(t-1) < 2/3 and t ≥ 3 is the number of parameters needed to represent the query arcs.
Cite as

Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2022.4,
  author =	{Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Katz, Matthew J. and Sharir, Micha},
  title =	{{Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.4},
  URN =		{urn:nbn:de:0030-drops-160126},
  doi =		{10.4230/LIPIcs.SoCG.2022.4},
  annote =	{Keywords: Intersection searching, Semi-algebraic range searching, Point-enclosure queries, Ray-shooting queries, Polynomial partitions, Cylindrical algebraic decomposition, Multi-level partition trees, Collision detection}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.3
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model

Authors: Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ ∈ C, the number of intersection points between the segments of A and those of B that lie in Δ. The problems considered in this paper have been studied by Chan (2020), who gave algorithms that solve them, in the standard real-RAM model, in O((n²/log²n) log^O(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε > 0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl (2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.
Cite as

Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2021.3,
  author =	{Aronov, Boris and de Berg, Mark and Cardinal, Jean and Ezra, Esther and Iacono, John and Sharir, Micha},
  title =	{{Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.3},
  URN =		{urn:nbn:de:0030-drops-154363},
  doi =		{10.4230/LIPIcs.ISAAC.2021.3},
  annote =	{Keywords: Computational geometry, Algebraic decision-tree model, Polynomial partitioning, Primal-dual range searching, Order types, Point location, Hierarchical partitions}
}
  • Refine by Type
  • 23 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 8 2025
  • 2 2024
  • 2 2023
  • 2 2022
  • 4 2021
  • Show More...

  • Refine by Author
  • 14 Ezra, Esther
  • 11 Sharir, Micha
  • 5 Agarwal, Pankaj K.
  • 4 Aronov, Boris
  • 2 Afshani, Peyman
  • Show More...

  • Refine by Series/Journal
  • 23 LIPIcs

  • Refine by Classification
  • 17 Theory of computation → Computational geometry
  • 4 Theory of computation
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 5 Polynomial partitioning
  • 3 Computational geometry
  • 2 Computational Geometry
  • 2 Intersection searching
  • 2 Ray shooting
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact