131 Search Results for "Wang, Haitao"

Volume

LIPIcs, Volume 332

41st International Symposium on Computational Geometry (SoCG 2025)

SoCG 2025, June 23-27, 2025, Kanazawa, Japan

Editors: Oswin Aichholzer and Haitao Wang

Document
DOI: 10.4230/LIPIcs.SoCG.2026.23
Shortest Paths in Geodesic Unit-Disk Graphs

Authors: Bruce W. Brewer and Haitao Wang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Let S be a set of n points in a polygon P with m vertices. The geodesic unit-disk graph G(S) induced by S has vertex set S and contains an edge between two vertices whenever their geodesic distance in P is at most one. In the weighted version, each edge is assigned weight equal to the geodesic distance between its endpoints; in the unweighted version, every edge has weight 1. Given a source point s ∈ S, we study the problem of computing shortest paths from s to all vertices of G(S). To the best of our knowledge, this problem has not been investigated previously. A naive approach constructs G(S) explicitly and then applies a standard shortest path algorithm for general graphs, but this requires quadratic time in the worst case, since G(S) may contain Ω(n²) edges. In this paper, we give the first subquadratic-time algorithms for this problem. For the weighted case, when P is a simple polygon, we obtain an O(m + n log³ n log² m)-time algorithm. For the unweighted case, we provide an O(m + n log n log² m)-time algorithm for simple polygons, and an O(√n (n+m)log(n+m))-time algorithm for polygons with holes.
Cite as

Bruce W. Brewer and Haitao Wang. Shortest Paths in Geodesic Unit-Disk Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.SoCG.2026.23,
  author =	{Brewer, Bruce W. and Wang, Haitao},
  title =	{{Shortest Paths in Geodesic Unit-Disk Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.23},
  URN =		{urn:nbn:de:0030-drops-258297},
  doi =		{10.4230/LIPIcs.SoCG.2026.23},
  annote =	{Keywords: unit-disk graph, geodesic distance, shortest paths, geodesic Voronoi diagrams, range emptiness queries, dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.95
An Optimal Algorithm for Computing Many Faces in Line Arrangements

Authors: Haitao Wang

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Given a set of m points and a set of n lines in the plane, we consider the classical problem of computing the faces of the arrangement of the lines that contain at least one point. We present an algorithm of O(m^{2/3} n^{2/3} + (n+m)log n) time for the problem. We also prove that this matches the lower bound under the algebraic decision tree model and thus our algorithm is optimal. In particular, when m = n, the runtime is O(n^{4/3}), which matches the worst case combinatorial complexity Ω(n^{4/3}) of all output faces. This is the first optimal algorithm since the problem was first studied more than three decades ago [Edelsbrunner, Guibas, and Sharir, SoCG 1988].
Cite as

Haitao Wang. An Optimal Algorithm for Computing Many Faces in Line Arrangements. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 95:1-95:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.SoCG.2026.95,
  author =	{Wang, Haitao},
  title =	{{An Optimal Algorithm for Computing Many Faces in Line Arrangements}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{95:1--95:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.95},
  URN =		{urn:nbn:de:0030-drops-259012},
  doi =		{10.4230/LIPIcs.SoCG.2026.95},
  annote =	{Keywords: Many faces, line arrangements, cuttings, \Gamma-algorithms, decision tree complexities}
}
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.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.46
Realizing Metric Spaces with Convex Obstacles

Authors: Sándor Kisfaludi-Bak and Leonidas Theocharous

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

Abstract
The presence of obstacles has a significant impact on distance computation, motion-planning, and visibility. These problems have been studied extensively in the planar setting, while our understanding of these problems in 3- and higher-dimensional spaces is still rudimentary. In this paper, we study the impact of different types of obstacles on the induced geodesic metric in 3-dimensional Euclidean space. We say that a finite metric space (X, dist_X) is approximately realizable by a collection 𝒯 of obstacles in ℝ³ if for any ε > 0 it can be embedded into (ℝ³⧵⋃_{T∈𝒯} T, dist_𝒯) with worst-case multiplicative distortion 1+ε, where dist_𝒯 denotes the geodesic distance in the free space induced by 𝒯. We focus on three key geometric properties of obstacles -convexity, disjointness, and fatness- and examine how dropping each one of them affects the existence of such embeddings. Our main result concerns dropping the fatness property: we demonstrate that any finite metric space is realizable with 1+ε worst-case multiplicative distortion using a collection of convex and pairwise disjoint obstacles in ℝ³, even if the obstacles are congruent and equilateral triangles. Based on the same construction, we can also show that if we require fatness but drop any of the other two properties instead, then we can still approximately realize any finite metric space. Our results have important implications on the approximability of tsp with obstacles, a natural variant of tsp introduced recently by Alkema et al. (ESA 2022). Specifically, we use the recent results of Banerjee et al. on tsp in doubling spaces (FOCS 2024) and of Chew et al. on distances among obstacles (Inf. Process. Lett. 2002) to show that tsp with obstacles admits a PTAS if the obstacles are convex, fat, and pairwise disjoint. If any of these three properties is dropped, then our results, combined with the APX-hardness of Metric tsp, demonstrate that tsp with obstacles is APX-hard.
Cite as

Sándor Kisfaludi-Bak and Leonidas Theocharous. Realizing Metric Spaces with Convex Obstacles. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 46:1-46:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2025.46,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Theocharous, Leonidas},
  title =	{{Realizing Metric Spaces with Convex Obstacles}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{46:1--46:21},
  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.46},
  URN =		{urn:nbn:de:0030-drops-249545},
  doi =		{10.4230/LIPIcs.ISAAC.2025.46},
  annote =	{Keywords: traveling salesman, geodesic distance}
}
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.21
Covering Weighted Points Using Unit Squares

Authors: Chaeyoon Chung, Jaegun Lee, and Hee-Kap Ahn

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

Abstract
Given a set of n points in d-dimensional space, each assigned a positive weight, we study the problem of finding k axis-parallel unit hypercubes that maximize the total weight of the points contained in their union. In this paper, we present both exact and (1 - ε)-approximation algorithms for the case of k = 2. We present an exact algorithm that runs in O(n²) time in the plane, improving the previous O(n² log² n)-time result. This algorithm generalizes to higher dimensions and larger k in O(n^{dk/2}) time for fixed d and k. We also present a (1 - ε)-approximation algorithm that runs in O(n log min{n, 1/ε} + 1/ε³) time for k = 2 in the plane, improving the best known result. Our approximation algorithm also extends to higher dimensions.
Cite as

Chaeyoon Chung, Jaegun Lee, and Hee-Kap Ahn. Covering Weighted Points Using Unit Squares. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ISAAC.2025.21,
  author =	{Chung, Chaeyoon and Lee, Jaegun and Ahn, Hee-Kap},
  title =	{{Covering Weighted Points Using Unit Squares}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{21:1--21:14},
  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.21},
  URN =		{urn:nbn:de:0030-drops-249292},
  doi =		{10.4230/LIPIcs.ISAAC.2025.21},
  annote =	{Keywords: Maximum coverage, Unit squares, Approximation algorithms}
}
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.GD.2025.16
Structural Parameterizations of k-Planarity

Authors: Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada

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

Abstract
The concept of k-planarity is extensively studied in the context of Beyond Planarity. A graph is k-planar if it admits a drawing in the plane in which each edge is crossed at most k times. The local crossing number of a graph is the minimum integer k such that it is k-planar. The problem of determining whether an input graph is 1-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor 2 - ε for any ε > 0 [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of k = 1, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case k ≥ 1 and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing 1-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most 2.
Cite as

Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada. Structural Parameterizations of k-Planarity. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.GD.2025.16,
  author =	{Gima, Tatsuya and Kobayashi, Yasuaki and Okada, Yuto},
  title =	{{Structural Parameterizations of k-Planarity}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{16:1--16:17},
  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.16},
  URN =		{urn:nbn:de:0030-drops-250021},
  doi =		{10.4230/LIPIcs.GD.2025.16},
  annote =	{Keywords: 1-planar graphs, local crossing number, beyond planarity, parameterized complexity, kernelization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.31
An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Authors: Bruce W. Brewer and Haitao Wang

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

Abstract
Given in the plane a set S of n points and a set of disks centered at these points, the disk graph G(S) induced by these disks has vertex set S and an edge between two vertices if their disks intersect. Note that the disks may have different radii. We consider the problem of computing shortest paths from a source point s ∈ S to all vertices in G(S) where the length of a path in G(S) is defined as the number of edges in the path. The previously best algorithm solves the problem in O(nlog² n) time. A lower bound of Ω(nlog n) is also known for this problem under the algebraic decision tree model. In this paper, we present an O(nlog n) time algorithm, which matches the lower bound and thus is optimal. Another virtue of our algorithm is that it is quite simple.
Cite as

Bruce W. Brewer and Haitao Wang. An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 31:1-31:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.ESA.2025.31,
  author =	{Brewer, Bruce W. and Wang, Haitao},
  title =	{{An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{31:1--31:8},
  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.31},
  URN =		{urn:nbn:de:0030-drops-244997},
  doi =		{10.4230/LIPIcs.ESA.2025.31},
  annote =	{Keywords: disk graphs, weighted Voronoi diagrams, shortest paths}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.62
Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering

Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen

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

Abstract
In a seminal work, Chierichetti et al. [Chierichetti et al., 2017] introduced the (t,k)-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most t times and at least 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O(1)- and O(t)-approximation for the k-center and the k-median objective, respectively. Recently, Carta et al. [Carta et al., 2024] studied this problem with the sum-of-radii objective and obtained a (6+ε)-approximation with running time O((k log_{1+ε}(k/ε))^k n^O(1)), i.e., fixed-parameter tractable in k. Here n is the input size. In this work, we design the first polynomial-time O(1)-approximation for (t,k)-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as k-center, that admit polynomial-time O(1)-approximations. This result also implies a polynomial-time O(1)-approximation for the Euclidean version of the problem, for which an f(k)⋅n^O(1)-time (1+ε)-approximation was known due to Drexler et al. [Drexler et al., 2023]. Here f is an exponential function of k. We are also able to extend our result to any arbitrary 𝓁 ≥ 2 number of colors when t = 1. This matches known results for the k-center and k-median objectives in this case. The significant disparity of sum-of-radii compared to k-center and k-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.
Cite as

Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen. Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bagherinezhad_et_al:LIPIcs.ESA.2025.62,
  author =	{Bagheri Nezhad, Sina and Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{62:1--62: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.62},
  URN =		{urn:nbn:de:0030-drops-245309},
  doi =		{10.4230/LIPIcs.ESA.2025.62},
  annote =	{Keywords: fair clustering, sum-of-radii clustering, approximation algorithms}
}
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.TQC.2025.5
Towards a Complexity-Theoretic Dichotomy for TQFT Invariants

Authors: Nicolas Bridges and Eric Samperton

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
We show that for any fixed (2+1)-dimensional TQFT over ℂ of either Turaev-Viro-Barrett-Westbury or Reshetikhin-Turaev type, the problem of (exactly) computing its invariants on closed 3-manifolds is either solvable in polynomial time, or else it is #𝖯-hard to (exactly) contract certain tensors that are built from the TQFT’s fusion category. Our proof is an application of a dichotomy result of Cai and Chen [J. ACM, 2017] concerning weighted constraint satisfaction problems over ℂ. We leave for future work the issue of reinterpreting the conditions of Cai and Chen that distinguish between the two cases (i.e. #𝖯-hard tensor contractions vs. polynomial time invariants) in terms of fusion categories. We expect that with more effort, our reduction can be improved so that one gets a dichotomy directly for TQFTs' invariants of 3-manifolds rather than more general tensors built from TQFTs' fusion categories.
Cite as

Nicolas Bridges and Eric Samperton. Towards a Complexity-Theoretic Dichotomy for TQFT Invariants. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bridges_et_al:LIPIcs.TQC.2025.5,
  author =	{Bridges, Nicolas and Samperton, Eric},
  title =	{{Towards a Complexity-Theoretic Dichotomy for TQFT Invariants}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.5},
  URN =		{urn:nbn:de:0030-drops-240548},
  doi =		{10.4230/LIPIcs.TQC.2025.5},
  annote =	{Keywords: Complexity, topological quantum field theory, dichotomy theorems, constraint satisfaction problems, tensor categories}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.14
Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Authors: Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, and Martin Nöllenburg

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the {dependency digraph} G_𝒫(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V(G_𝒫(I))| √δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√{nm}) time, which improves the best known classical upper bound when m ∈ Ω(n^{1.4}).
Cite as

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, and Martin Nöllenburg. Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{caroppo_et_al:LIPIcs.WADS.2025.14,
  author =	{Caroppo, Susanna and Da Lozzo, Giordano and Di Battista, Giuseppe and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.14},
  URN =		{urn:nbn:de:0030-drops-242454},
  doi =		{10.4230/LIPIcs.WADS.2025.14},
  annote =	{Keywords: Dynamic Programming, Quantum Algorithms, Quantum Random Access Memory}
}
  • Refine by Type
  • 130 Document/PDF
  • 98 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 4 2026
  • 101 2025
  • 6 2024
  • 3 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 33 Wang, Haitao
  • 7 Xue, Jie
  • 5 Chan, Timothy M.
  • 3 Buchin, Kevin
  • 3 Liu, Gang
  • Show More...

  • Refine by Series/Journal
  • 130 LIPIcs

  • Refine by Classification
  • 88 Theory of computation → Computational geometry
  • 30 Theory of computation → Design and analysis of algorithms
  • 8 Mathematics of computing → Algebraic topology
  • 8 Mathematics of computing → Combinatorics
  • 7 Mathematics of computing → Geometric topology
  • Show More...

  • Refine by Keyword
  • 7 shortest paths
  • 5 Fréchet distance
  • 4 geodesic distance
  • 3 Multiparameter persistence
  • 3 approximation algorithms
  • 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