DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.81

Counting Unit Circular Arc Intersections

Authors: Haitao Wang

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

Given a set of n circular arcs of the same radius in the plane, we consider the problem of computing the number of intersections among the arcs. The problem was studied before and the previously best algorithm solves the problem in O(n^{4/3+ε}) time [Agarwal, Pellegrini, and Sharir, SIAM J. Comput., 1993], for any constant ε > 0. No progress has been made on the problem for more than 30 years. We present a new algorithm of O(n^{4/3}log^{16/3} n) time and improve it to O(n^{1+ε}+K^{1/3}n^{2/3}((n²)/(n+K))^{ε}log^{16/3}n) time for small K, where K is the number of intersections of all arcs.

Cite as

Haitao Wang. Counting Unit Circular Arc Intersections. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 81:1-81:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.STACS.2026.81,
  author =	{Wang, Haitao},
  title =	{{Counting Unit Circular Arc Intersections}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{81:1--81:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.81},
  URN =		{urn:nbn:de:0030-drops-255707},
  doi =		{10.4230/LIPIcs.STACS.2026.81},
  annote =	{Keywords: circular arc intersections, unit circles, arrangements, cuttings, segment intersections}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.54

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm

Authors: Stefan Hougardy and Bart Zondervan

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

In the Strip Packing problem, we are given a vertical strip of fixed width and unbounded height, along with a set of axis‑parallel rectangles. The task is to place all rectangles within the strip, without overlaps, while minimizing the height of the packing. This problem is known to be NP-hard. The Bottom-Left Algorithm is a simple and widely used heuristic for Strip Packing. Given a fixed order of the rectangles, it places them one by one, always choosing the lowest feasible position in the strip and, in case of ties, the leftmost one. Baker, Coffman, and Rivest proved in 1980 that the Bottom-Left Algorithm has approximation ratio 3 if the rectangles are sorted by decreasing width [Brenda S. Baker et al., 1980]. For the past 45 years, no alternative ordering has been found that improves this bound. We introduce a new rectangle ordering and show that with this ordering the Bottom-Left Algorithm achieves a 13/6 approximation for the Strip Packing problem.

Cite as

Stefan Hougardy and Bart Zondervan. A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hougardy_et_al:LIPIcs.STACS.2026.54,
  author =	{Hougardy, Stefan and Zondervan, Bart},
  title =	{{A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.54},
  URN =		{urn:nbn:de:0030-drops-255432},
  doi =		{10.4230/LIPIcs.STACS.2026.54},
  annote =	{Keywords: Approximation Algorithm, Strip Packing, Bottom-Left Algorithm, Rectangle Packing}
}

Document

DOI: 10.4230/LIPIcs.CSL.2026.29

Parametric Iteration in Resource Theories

Authors: Alessandro Di Giorgio, Pawel Sobocinski, and Niels Voorneveld

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract

Many algorithms are specified with respect to a fixed but unknown parameter. Examples of this are especially common in cryptography, where protocols often feature a security parameter such as the bit length of a secret key. Our aim is to capture this phenomenon in a more abstract setting. We focus on resource theories - general calculi of processes with a string diagrammatic syntax - introducing a general parametric iteration construction. By instantiating this construction within the Markov category of probabilistic Boolean circuits and equipping it with a suitable metric, we are able to capture the notion of negligibility via asymptotic equivalence, in a compositional way. This allows us to use diagrammatic reasoning to prove simple cryptographic theorems - for instance, proving that guessing a randomly generated key has negligible success.

Cite as

Alessandro Di Giorgio, Pawel Sobocinski, and Niels Voorneveld. Parametric Iteration in Resource Theories. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{digiorgio_et_al:LIPIcs.CSL.2026.29,
  author =	{Di Giorgio, Alessandro and Sobocinski, Pawel and Voorneveld, Niels},
  title =	{{Parametric Iteration in Resource Theories}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{29:1--29:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.29},
  URN =		{urn:nbn:de:0030-drops-254541},
  doi =		{10.4230/LIPIcs.CSL.2026.29},
  annote =	{Keywords: Markov categories, Cryptography, String diagrams, Asymptotic equivalence}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.71

Lower Bounds on FSS from Dynamic Data Structures

Authors: Niv Gilboa and Daniel Weber

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

In Function Secret Sharing (FSS), a dealer with a given function f: {0,1}ⁿ → 𝔾 from n bits to a commutative group 𝔾 such that f is in a function class ℱ shares succinct keys with two properties. Evaluating each key separately on a common input x results in additive shares of f(x) and any subset of the keys does not provide information on f. Two-party FSS schemes which are reducible to One-way Functions (OWF) have applications in cryptography, complexity, and in practical data security systems. We establish a two-way transformation between a two-party FSS scheme for a function class ℱ, which is black-box reducible to an OWF, or even black-box reducible to a family of Pseudo-Random Functions (PRF) and a dynamic data structure that supports range queries on ℱ. A data structure of this type enables dynamically adding functions to a multiset of functions F ⊆ ℱ, and answering range queries on the output of F, i.e., returning ∑_{f ∈ F} f(x) for a query x. The data structures are defined in one of several models which abstract RAM. The correspondence together with known lower bounds on the update time and the query time in data structures leads to the first non-trivial lower bounds on FSS schemes which are black-box reducible to PRF. These lower bounds apply to FSS schemes with polynomial key size and include: - For ℱ^d_{box}, the class of all functions which assign a constant group element β ∈ 𝔾 to any input in a specified d-dimensional box and 0 to all other inputs: if the key sharing function, Gen, runs in time polynomial in n and the evaluation function is Eval then: - If d ≥ 2 and 𝔾 = ℤ₂ then Eval’s running time is Ω ((n^{3/2})/(log³ n)). - If d ≥ 2 and 𝔾 is cyclic such that log |𝔾| = (1 + ε) n then Eval’s running time is Ω ((n/(log n)) ²). - If d > 2 is a constant and further, Gen and Eval correspond to operations on data structures in the Oblivious Group Model (this includes all known FSS from OWF techniques), then the product of Eval’s time and the key size is Ω(n^{d-1}). - For ℱ_{mono}, the class of all monomials ax^b ∈ 𝔽_{2ⁿ}[X] such that b ≤ B, assuming n^{ω(1)} ≤ B ≤ 2^{n/4}: if Gen runs in polynomial time, then Eval’s running time is Ω ((n √{log B})/(log² n)).

Cite as

Niv Gilboa and Daniel Weber. Lower Bounds on FSS from Dynamic Data Structures. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 71:1-71:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gilboa_et_al:LIPIcs.ITCS.2026.71,
  author =	{Gilboa, Niv and Weber, Daniel},
  title =	{{Lower Bounds on FSS from Dynamic Data Structures}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{71:1--71:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.71},
  URN =		{urn:nbn:de:0030-drops-253585},
  doi =		{10.4230/LIPIcs.ITCS.2026.71},
  annote =	{Keywords: FSS, Data Structures, Lower Bounds, Black-Box Reductions}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.31

Delaunay Triangulations with Predictions

Authors: Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P of n points in the plane and a triangulation G that serves as a "prediction" of the Delaunay triangulation, we would like to use G to compute the correct Delaunay triangulation DT(P) more quickly when G is "close" to DT(P). We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define D to be the number of edges in G that are not in DT(P). We present a deterministic algorithm to compute DT(P) from G in O(n + Dlog³ n) time, and a randomized algorithm in O(n+Dlog n) expected time, the latter of which is optimal in terms of D. 2) Let R be a random subset of the edges of DT(P), where each edge is chosen independently with probability ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{vio} to be the maximum number of points of P strictly inside the circumcircle of a triangle in G (the number is 0 if G is equal to DT(P)). We present a deterministic algorithm to compute DT(P) from G in O(nlog^*n + nlog d_{vio}) time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.

Cite as

Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos. Delaunay Triangulations with Predictions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ITCS.2026.31,
  author =	{Cabello, Sergio and Chan, Timothy M. and Giannopoulos, Panos},
  title =	{{Delaunay Triangulations with Predictions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{31:1--31:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.31},
  URN =		{urn:nbn:de:0030-drops-253186},
  doi =		{10.4230/LIPIcs.ITCS.2026.31},
  annote =	{Keywords: Delaunay Triangulation, Minimum Spanning Tree, Algorithms with Predictions}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.3

Circle-Segment Intersection Queries in Connected Geometric Graphs

Authors: Peyman Afshani, Yannick Bosch, and Sabine Storandt

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

Abstract

In this paper, we study the problem of efficiently reporting all intersections between a given set of line segments in the plane and a query circle, focusing on the case where the segments form the edges of a connected geometric graph. While previous data structures for circle-segment intersection queries on general segment sets incur high space or query time costs, we exploit the connectivity of the input to obtain significantly improved performance. In fact, we propose a new circle-segment intersection data structure that can be constructed in 𝒪((n + C) log³ n) time and space on connected graphs with n edges and C edge crossings. It answers intersection queries in 𝒪(k log³ n) time, where k denotes the output size. Our method relies on the construction of efficient circle-graph intersection oracles as well as a novel linear-time algorithm to partition the edges of the graph into balanced, connected components, which might be of independent interest. In a proof-of-concept experimental study on real-world road networks, we show that our novel data structure also performs well in practice. Even on networks with millions of edges, the construction time is within minutes and queries are answered in a few milliseconds.

Cite as

Peyman Afshani, Yannick Bosch, and Sabine Storandt. Circle-Segment Intersection Queries in Connected Geometric Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ISAAC.2025.3,
  author =	{Afshani, Peyman and Bosch, Yannick and Storandt, Sabine},
  title =	{{Circle-Segment Intersection Queries in Connected Geometric Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{3:1--3:16},
  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.3},
  URN =		{urn:nbn:de:0030-drops-249114},
  doi =		{10.4230/LIPIcs.ISAAC.2025.3},
  annote =	{Keywords: Intersection data structure, Graph partitioning, Dobkin-Kirkpatrick hierarchy}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.21

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

Authors: Parinya Chalermsook, Ly Orgo, and Minoo Zarsav

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

This paper considers the Zarankiewicz problem in bipartite graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Let Z(n;k) be the maximum number of edges in a bipartite graph with n nodes and is free of a k-by-k biclique. Note that Z(n;k) ∈ Ω(nk) for all "natural" graph classes. Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while we show that Z(n;k) ≤ 9n(k-1) for graphs of Ferrers dimension three, Z(n;k) ∈ Ω(n k ⋅ (log n)/(log log n)) for Ferrers dimension four graphs (Chan & Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of 2n(k-1) for chordal bipartite graphs and 54n(k-1) for grid intersection graphs (GIG), a prominent graph class residing in four Ferrers dimensions and capturing planar bipartite graphs as well as bipartite intersection graphs of rectangles. Previously, the best-known bound for GIG was Z(n;k) ∈ O(2^{O(k)} n), implied by the results of Fox & Pach (2006) and Mustafa & Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics.

Cite as

Parinya Chalermsook, Ly Orgo, and Minoo Zarsav. On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.GD.2025.21,
  author =	{Chalermsook, Parinya and Orgo, Ly and Zarsav, Minoo},
  title =	{{On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.21},
  URN =		{urn:nbn:de:0030-drops-250074},
  doi =		{10.4230/LIPIcs.GD.2025.21},
  annote =	{Keywords: Bipartite graph classes, extremal graph theory, geometric intersection graphs, Zarankiewicz problem, bicliques}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.7

On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits

Authors: Matthias Artmann, Andreas Padalkin, and Christian Scheideler

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

In programmable matter, we consider a large number of tiny, primitive computational entities called particles that run distributed algorithms to control global properties of the particle structure. Shape formation problems, where the particles have to reorganize themselves into a desired shape using basic movement abilities, are particularly interesting. In the related shape containment problem, the particles are given the description of a shape S and have to find maximally scaled representations of S within the initial configuration, without movements. For example, if S is a triangle, they have to identify the largest subsets of particles that already form a triangle. While the shape formation problem is being studied extensively, no attention has been given to the shape containment problem, which may have additional uses besides shape formation, such as detecting structural flaws. In this paper, we consider the shape containment problem within the geometric amoebot model for programmable matter, using its reconfigurable circuit extension to enable the instantaneous transmission of primitive signals on connected subsets of particles. We first prove a lower runtime bound of Ω (√n) synchronous rounds for the general problem, where n is the number of particles. Then, we present simple and efficient primitives for identifying subsets that form the desired shape. Using these primitives, we construct a large class of shapes which we call snowflakes. This class contains, among others, all shapes composed of parallelograms and hexagons, and the class of star convex shapes. Let k be the maximum scale of the considered shape in a given amoebot structure. If the shape is star convex, we solve it within 𝒪 (log² k) rounds. If it is a snowflake but not star convex, we solve it within 𝒪 (√n log n) rounds.

Cite as

Matthias Artmann, Andreas Padalkin, and Christian Scheideler. On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{artmann_et_al:LIPIcs.DISC.2025.7,
  author =	{Artmann, Matthias and Padalkin, Andreas and Scheideler, Christian},
  title =	{{On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.7},
  URN =		{urn:nbn:de:0030-drops-248240},
  doi =		{10.4230/LIPIcs.DISC.2025.7},
  annote =	{Keywords: Programmable matter, amoebot model, reconfigurable circuits, shape containment}
}

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.64

A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees

Authors: Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, and Tord Stordalen

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

Abstract

Indexing data is a fundamental problem in computer science. The input is a set S of n distinct integers from a universe 𝒰. Indexing queries take a value q ∈ 𝒰 and return the membership, predecessor or rank of q in S. A range query takes two values q, r ∈ 𝒰 and returns the set S ∩ [q,r]. Recently, various papers study a special case where the the input data behaves in an approximately piece-wise linear way. Given the sorted (rank,value) pairs, and given some constant ε, one wants to maintain a small number of axis-disjoint line-segments such that, for each rank, the value is within ± ε of the corresponding line-segment. Ferragina and Vinciguerra (VLDB 2020) observe that this geometric problem is useful for solving indexing problems, particularly when the number of line-segments is small compared to the size of the dataset. We study the dynamic version of this geometric problem. In the dynamic setting, inserting or deleting just one data point may cause up to three line-segments to be merged, or one line-segment to be split at most three-way. To determine and compute this, we use techniques from dynamic maintenance of convex hulls, and provide new algorithms with worst-case guarantees, including an O(log n) algorithm to compute a separating line between two non-intersecting convex hulls - an operation previously missing from the literature. We then use our fully-dynamic geometry-based subroutine in an indexing data structure, combining it with a natural hashing technique. The resulting indexing data structure has theoretically efficient worst-case guarantees in expectation. We compare its practical performance to the solution of Ferragina and Vinciguerra, which was shown to perform better in certain structured settings [Sun, Zhou, Li VLDB 2023]. Our empirical analysis shows that our solution supports more efficient range queries in the special case where the update sequence contains many deletions.

Cite as

Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, and Tord Stordalen. A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gaede_et_al:LIPIcs.ESA.2025.64,
  author =	{G{\ae}de, Emil Toftegaard and van der Hoog, Ivor and Rotenberg, Eva and Stordalen, Tord},
  title =	{{A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{64:1--64:18},
  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.64},
  URN =		{urn:nbn:de:0030-drops-245323},
  doi =		{10.4230/LIPIcs.ESA.2025.64},
  annote =	{Keywords: Algorithms Engineering, Data Structures, Indexing, Convex Hulls}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.114

A Deterministic Partition Tree and Applications

Authors: Haitao Wang

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

Abstract

In this paper, we present a deterministic variant of Chan’s randomized partition tree [Discret. Comput. Geom., 2012]. This result leads to numerous applications. In particular, for d-dimensional simplex range counting (for any constant d ≥ 2), we construct a data structure using O(n) space and O(n^{1+ε}) preprocessing time, such that each query can be answered in o(n^{1-1/d}) time (specifically, O(n^{1-1/d} / log^Ω(1) n) time), thereby breaking an Ω(n^{1-1/d}) lower bound known for the semigroup setting. Notably, our approach does not rely on any bit-packing techniques. We also obtain deterministic improvements for several other classical problems, including simplex range stabbing counting and reporting, segment intersection detection, counting and reporting, ray-shooting among segments, and more. Similar to Chan’s original randomized partition tree, we expect that additional applications will emerge in the future, especially in situations where deterministic results are preferred.

Cite as

Haitao Wang. A Deterministic Partition Tree and Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 114:1-114:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.ESA.2025.114,
  author =	{Wang, Haitao},
  title =	{{A Deterministic Partition Tree and Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{114:1--114:17},
  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.114},
  URN =		{urn:nbn:de:0030-drops-245836},
  doi =		{10.4230/LIPIcs.ESA.2025.114},
  annote =	{Keywords: partition trees, simplex range searching, segment intersection queries, ray-shootings, multi-level data structures}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.84

Property Testing of Curve Similarity

Authors: Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong

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

Abstract

We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is given access to the input curves via a query oracle: a query returns the set of vertices of the curve that lie within a radius δ of a specified vertex of the other curve. The goal is to use a small number of queries to determine with constant probability whether the two curves are similar (i.e., their discrete Fréchet distance is at most δ) or they are "ε-far" (for 0 < ε < 2) from being similar, i.e., more than an ε-fraction of the two curves must be ignored for them to become similar. We present two algorithms which are sublinear assuming that the curves are t-approximate shortest paths in the ambient metric space, for some t ≪ n. The first algorithm uses O(t/ε log t/ε) queries and is given the value of t in advance. The second algorithm does not have explicit knowledge of the value of t and therefore needs to gain implicit knowledge of the straightness of the input curves through its queries. We show that the discrete Fréchet distance can still be tested using roughly O({t³+t² log n}/ε) queries ignoring logarithmic factors in t. Our algorithms work in a matrix representation of the input and may be of independent interest to matrix testing. Our algorithms use a mild uniform sampling condition that constrains the edge lengths of the curves, similar to a polynomially bounded aspect ratio. Applied to testing the continuous Fréchet distance of t-straight curves, our algorithms can be used for (1+ε')-approximate testing using essentially the same bounds as stated above with an additional factor of poly(1/(ε')).

Cite as

Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong. Property Testing of Curve Similarity. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ESA.2025.84,
  author =	{Afshani, Peyman and Buchin, Maike and Driemel, Anne and Richter, Marena and Wong, Sampson},
  title =	{{Property Testing of Curve Similarity}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{84:1--84:16},
  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.84},
  URN =		{urn:nbn:de:0030-drops-245522},
  doi =		{10.4230/LIPIcs.ESA.2025.84},
  annote =	{Keywords: Fr\'{e}chet distance, Trajectory Analysis, Curve Similarity, Property Testing, Monotonicity Testing}
}

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

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.45

Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them

Authors: Clément L. Canonne, Yun Li, and Seeun William Umboh

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

Abstract

Local Computation Algorithms (LCA), as introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a type of ultra-efficient algorithms which, given access to a (large) input for a given computational task, are required to provide fast query access to a consistent output solution, without maintaining a state between queries. This paradigm of computation in particular allows for hugely distributed algorithms, where independent instances of a given LCA provide consistent access to a common output solution. The past decade has seen a significant amount of work on LCAs, by and large focusing on graph problems. In this paper, we initiate the study of Local Computation Algorithms for perhaps the archetypal combinatorial optimization problem, Knapsack. We first establish strong impossibility results, ruling out the existence of any non-trivial LCA for Knapsack as several of its relaxations. We then show how equipping the LCA with additional access to the Knapsack instance, namely, weighted item sampling, allows one to circumvent these impossibility results, and obtain sublinear-time and query LCAs. Our positive result draws on a connection to the recent notion of reproducibility for learning algorithms (Impagliazzo, Lei, Pitassi, and Sorrell, 2022), a connection we believe to be of independent interest for the design of LCAs.

Cite as

Clément L. Canonne, Yun Li, and Seeun William Umboh. Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.APPROX/RANDOM.2025.45,
  author =	{Canonne, Cl\'{e}ment L. and Li, Yun and Umboh, Seeun William},
  title =	{{Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{45:1--45:21},
  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.45},
  URN =		{urn:nbn:de:0030-drops-244111},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.45},
  annote =	{Keywords: Local computation algorithms, Knapsack, algorithms, lower bounds}
}

50 Search Results for "Chazelle, Bernard"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message