234 Search Results for "Ahn, Hee-Kap"

Volume

LIPIcs, Volume 367

42nd International Symposium on Computational Geometry (SoCG 2026)

SoCG 2026, New Brunswick, NJ, USA, June 2-5, 2026

Editors: Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Volume

LIPIcs, Volume 212

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

ISAAC 2021, December 6-8, 2021, Fukuoka, Japan

Editors: Hee-Kap Ahn and Kunihiko Sadakane

Document
DOI: 10.4230/LIPIcs.SWAT.2026.40
Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Authors: Anastasiia Tkachenko and Haitao Wang

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
For a set 𝒟 of disks in the plane, its disk graph G(𝒟) is the graph with vertex set 𝒟, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set 𝒟 of n weighted disks, computing a maximum independent set of G(𝒟) is NP-hard. In this paper, we present an O(n³log n)-time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of 𝒟. This setting has been studied previously for disks of equal radius, for which an O(n^{37/11})-time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an O(n³log² n)-time algorithm for the dispersion problem on a set of n disks in convex position: given an integer k, compute a subset of k disks that maximizes the minimum pairwise distance among all disks in the subset.
Cite as

Anastasiia Tkachenko and Haitao Wang. Maximum Independent Sets in Disk Graphs with Disks in Convex Position. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tkachenko_et_al:LIPIcs.SWAT.2026.40,
  author =	{Tkachenko, Anastasiia and Wang, Haitao},
  title =	{{Maximum Independent Sets in Disk Graphs with Disks in Convex Position}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.40},
  URN =		{urn:nbn:de:0030-drops-260766},
  doi =		{10.4230/LIPIcs.SWAT.2026.40},
  annote =	{Keywords: disk graphs, independent sets, convex position, dispersion}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.14
Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

Authors: Jaehoon Chung

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study a variant of a polygon partition problem, introduced by Chung, Iwama, Liao, and Ahn [ISAAC'25]. Given orthogonal unit vectors 𝐮,𝐯 ∈ ℝ² and a polygon P with n vertices, we partition P into connected pieces by cuts parallel to 𝐯 such that each resulting subpolygon has width at most one in direction 𝐮. We consider the value version, which asks for the minimum number of strips, and the reporting version, which outputs a compact encoding of the cuts in an optimal strip partition. We give efficient algorithms and lower bounds for both versions on three classes of polygons of increasing generality: convex, simple, and self-overlapping. For convex polygons, we solve the value version in O(log n) time and the reporting version in O(h log (1 + n/h)) time, where h is the width of P in direction 𝐮. We prove matching lower bounds in the decision-tree model, showing that the reporting algorithm is input-sensitive optimal with respect to h. For simple polygons, we present O(n log n)-time, O(n)-space algorithms for both versions and prove an Ω(n) lower bound. For self-overlapping polygons, we extend the approach for simple polygons to obtain O(n log n)-time, O(n)-space algorithms for both versions, and we prove a matching Ω(n log n) lower bound in the algebraic computation-tree model via a reduction from the δ-closeness problem. Our approach relies on a lattice-theoretic formulation of the problem. We represent strip partitions as antichains of intervals in the Clarke-Cormack-Burkowski lattice, originally developed for minimal-interval semantics in information retrieval. Within this lattice framework, we design a dynamic programming algorithm that uses the lattice operations of meet and join. To the best of our knowledge, this is the first geometric application of the Clarke-Cormack-Burkowski lattice.
Cite as

Jaehoon Chung. Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chung:LIPIcs.SWAT.2026.14,
  author =	{Chung, Jaehoon},
  title =	{{Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.14},
  URN =		{urn:nbn:de:0030-drops-260506},
  doi =		{10.4230/LIPIcs.SWAT.2026.14},
  annote =	{Keywords: Polygon partitioning, Strip partition, Lattice, Self-overlapping curves}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.29
Bichromatic Classifications of Points Using Strips

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

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Given a set of n points in the plane, each colored either blue or red, we study the problem of finding a strip that separates the blue points from the red points. Specifically, we consider the following two variants: (1) locating a strip that contains no red points while maximizing the number of blue points within the strip, and (2) locating a strip that contains all blue points while minimizing the number of red points within the strip. For variant (1), we present an O(n²)-time algorithm, improving upon the previously best O(n²log n)-time result. We also show that this running time is optimal under the standard 3SUM conjecture. We also give an output-sensitive algorithm with running time O(k_{opt} n log n) that returns a strip, where k_{opt} is the number of blue points not contained within the strip in an optimal solution. We extend our results to the case of up to t parallel strips, obtaining an O(n²log n)-time algorithm. For variant (2), an optimal Θ(nlog n)-time algorithm is known for t = 1. We show 3SUM-hardness for t = 2 and give an O(n²)-time algorithm. For any t ≥ 3, we present an O(n²log n)-time algorithm.
Cite as

Jaegun Lee, Chaeyoon Chung, and Hee-Kap Ahn. Bichromatic Classifications of Points Using Strips. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.SWAT.2026.29,
  author =	{Lee, Jaegun and Chung, Chaeyoon and Ahn, Hee-Kap},
  title =	{{Bichromatic Classifications of Points Using Strips}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.29},
  URN =		{urn:nbn:de:0030-drops-260659},
  doi =		{10.4230/LIPIcs.SWAT.2026.29},
  annote =	{Keywords: Bichromatic Classification, Separation, Strip, Duality}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.35
Path-Reporting Distance Oracles for Vertex-Labeled Graphs

Authors: Ofer Neiman and Alon Spector

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Let G = (V,E) be a weighted undirected graph, with n vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal work of [Thorup and Zwick, 2005], given an integer k ≥ 1, provides such an oracle with stretch 2k-1, query time O(k), and size O(k⋅ n^{1+1/k}). Furthermore, this oracle can also report a path in G corresponding to the returned distance. In this paper we focus on vertex-labeled graphs, in which each vertex is given a label from a set L of size 𝓁. A vertex-label distance oracle answers queries of the form (v,λ), where v ∈ V and λ ∈ L, by reporting (an approximation to) the distance from v to the closest vertex of label λ. Following [Danny Hermelin et al., 2011], it was shown in [Chechik, 2012] that for any integer k > 1, there exists a vertex-label distance oracle with stretch 4k-5, query time O(k), and size O(k⋅ n⋅ 𝓁^{1/k}). This state-of-the-art result suffers from two main drawbacks: The stretch is roughly a factor of 2 larger than in [Thorup and Zwick, 2005], and it is not path-reporting. We address these concerns in this work, and provide the following results. - First, we devise a path-reporting vertex-label distance oracle, at the cost of a slight increase in stretch and size. For any constant 0 < ε < 1, our oracle has stretch (4k-5)⋅(1+ε), query time O(k), and size O(n^{1+o(1)}⋅ 𝓁^{1/k}). - Second, we show how to improve the stretch to the optimal 2k-1, at the cost of mildly increasing the query time. Specifically, we devise a vertex-label distance oracle with stretch 2k-1, query time O(𝓁^{1/k}⋅log n), and size O(k⋅ n⋅ 𝓁^{1/k}).
Cite as

Ofer Neiman and Alon Spector. Path-Reporting Distance Oracles for Vertex-Labeled Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{neiman_et_al:LIPIcs.SWAT.2026.35,
  author =	{Neiman, Ofer and Spector, Alon},
  title =	{{Path-Reporting Distance Oracles for Vertex-Labeled Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.35},
  URN =		{urn:nbn:de:0030-drops-260719},
  doi =		{10.4230/LIPIcs.SWAT.2026.35},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Distance Oracles}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.1
Covering and Partitioning Complex Objects with Small Pieces

Authors: Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade

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

Abstract
We study the problems of covering or partitioning a polygon P (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contained in an axis-aligned unit square. For covering, we seek to write P as a union of small pieces, and in partitioning, we furthermore require the pieces to be pairwise interior-disjoint. We show that these problems are in fact equivalent: Optimum covers and partitions have the same number of pieces. For covering, a natural local search algorithm repeatedly attempts to replace k pieces from a candidate cover with k-1 pieces. In two dimensions and for sufficiently large k, we show that when no such swap is possible, the cover is a 1+ O(1/√k) approximation, hence obtaining the first PTAS for the problem. Prior to our work, the only known algorithm was a 13-approximation that only works for polygons without holes [Abrahamsen and Rasmussen, SODA 2025]. In contrast, in the three dimensional version of the problem, for a polyhedron P of complexity n, we show that it is NP-hard to approximate an optimal cover or partition to within a factor that is logarithmic in n, even if P is simple, i.e., has genus 0 and no holes.
Cite as

Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade. Covering and Partitioning Complex Objects with Small Pieces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2026.1,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Browne, Reilly and Goswami, Mayank and Kasthurirangan, Prahlad Narasimhan and Kleist, Linda and Mitchell, Joseph S. B. and Polishchuk, Valentin and Stade, Jack},
  title =	{{Covering and Partitioning Complex Objects with Small Pieces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{1:1--1:16},
  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.1},
  URN =		{urn:nbn:de:0030-drops-258077},
  doi =		{10.4230/LIPIcs.SoCG.2026.1},
  annote =	{Keywords: Covering, partitioning, polygon, small piece, PTAS}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.4
Dynamic Nearest-Neighbor Searching Under General Metrics in ℝ³ and Its Applications

Authors: Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir

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

Abstract
Let K be a compact, centrally-symmetric, strictly-convex region in ℝ³, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as ‖⋅‖_K. Let 𝒦 be a set of n homothetic copies of K. This paper contains two main sets of results: (i) For a storage parameter s ∈ [n,n³], 𝒦 can be preprocessed in O^*(s) expected time into a data structure of size O^*(s), so that for a query homothet K₀ of K, an intersection-detection query (determine whether K₀ intersects any member of 𝒦, and if so, report such a member) or a nearest-neighbor query (return the member of 𝒦 whose ‖⋅‖_K-distance from K₀ is smallest) can be answered in O^*(n/s^{1/3}) time; all k homothets of 𝒦 intersecting K₀ can be reported in additional O(k) time. In addition, the data structure supports insertions/deletions in O^*(s/n) amortized expected time per operation. Here the O^*(⋅) notation hides factors of the form n^ε, where ε > 0 is an arbitrarily small constant, and the constant of proportionality depends on ε. (ii) Let 𝒢(𝒦) denote the intersection graph of 𝒦. Using the above data structure, breadth-first or depth-first search on 𝒢(𝒦) can be performed in O^*(n^{3/2}) expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of 𝒦 can be solved in O^*(n^{62/39}) expected time. Dijkstra’s shortest-path algorithm, as well as Prim’s MST algorithm, on a ‖⋅‖_K-proximity graph on n points in ℝ³, with edges weighted by ‖⋅‖_K, can also be performed in O^*(n^{3/2}) time.
Cite as

Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. Dynamic Nearest-Neighbor Searching Under General Metrics in ℝ³ and Its Applications. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2026.4,
  author =	{Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha},
  title =	{{Dynamic Nearest-Neighbor Searching Under General Metrics in \mathbb{R}³ and Its Applications}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{4:1--4: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.4},
  URN =		{urn:nbn:de:0030-drops-258102},
  doi =		{10.4230/LIPIcs.SoCG.2026.4},
  annote =	{Keywords: Homothets, Minkowski metric, Shallow cuttings, Nearest-neighbor searching, Intersection and proximity graphs, Reverse-shortest-path problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.7
Computing L_∞ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness

Authors: Sebastian Angrick, Kevin Buchin, Geri Gokaj, and Marvin Künnemann

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

Abstract
To measure the similarity of the shape of point sets, rather than their mere closeness in space, various notions of a Hausdorff distance under translation have been investigated. Specifically, let P and Q denote point sets of n and m points, respectively, in ℝ^d. We consider the task of computing the minimum distance d(P,Q+τ) over an admissible set of translations τ ∈ T, where d(⋅, ⋅) denotes the Hausdorff distance under the L_∞-norm. As variants, we distinguish between continuous (T = ℝ^d) or discrete (T is a given finite set of t translations) as well as directed or undirected (choosing the directed or undirected Hausdorff distance for d(⋅, ⋅)). We seek to apply the paradigm of fine-grained complexity to understand the complexity of these variants, and in particular: How is the running time influenced by the dimension d, the relationship between n and m, and the specific choice of variant? As our main results, we obtain: - The asymmetric definition of the most studied variant, the continuous directed Hausdorff distance, results in an intrinsically asymmetric time complexity: While (Chan, SoCG'23) established a symmetric Õ((nm)^{d/2}) upper bound for all d ≥ 3 and proved it to be conditionally optimal for combinatorial algorithms whenever m ≤ n, we show that this lower bound does not hold for the case n ≪ m, by providing a combinatorial, almost-linear-time algorithm for d = 3 and n = m^{o(1)}. We further prove general, i.e., non-combinatorial, conditional lower bounds for d ≥ 3, in particular: (1) m^{⌊d/2⌋ - o(1)} for small n and (2) n^{d/2 - o(1)} for d = 3 and small m. - We observe that the directed and undirected case is closely related, in particular, all our lower bounds for d ≥ 3 hold for both the directed and undirected variant. A remarkable exception is the case of d = 1 for which we provide a conditional separation. Specifically, in contrast to the undirected variants being solvable in near-linear time (Rote, IPL'91), we show that the directed variants are at least as hard as the additive problem MaxConv LowerBound introduced in (Cygan, Mucha, Wegrzycki and Wlodarczyk, TALG'19). - We show that the discrete variants reduce to a variant of 3SUM for d ≤ 3. This gives a barrier in proving a tight lower bound of these variants under the Orthogonal Vectors Hypothesis (OVH); in contrast, the continuous variants admit a tight conditional lower bound under OVH in d = 2 (Bringmann, Nusser, JoCG'21). These results reveal an intricate interplay of dimensionality, symmetry and discreteness in determining the fine-grained complexity of computing Hausdorff distances under translation.
Cite as

Sebastian Angrick, Kevin Buchin, Geri Gokaj, and Marvin Künnemann. Computing L_∞ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.SoCG.2026.7,
  author =	{Angrick, Sebastian and Buchin, Kevin and Gokaj, Geri and K\"{u}nnemann, Marvin},
  title =	{{Computing L\underline∞ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-258131},
  doi =		{10.4230/LIPIcs.SoCG.2026.7},
  annote =	{Keywords: Hausdorff Distance, Fine-Grained Complexity, Computational Geometry, Translation-Invariant Similarity Measures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.2
On the Maximum Number of Tangencies Among 1-Intersecting Curves

Authors: Eyal Ackerman and Balázs Keszegh

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

Abstract
According to a conjecture of Pach, there are O(n) tangent pairs among any family of n Jordan arcs in which every pair of arcs has precisely one common point and no three arcs share a common point. This conjecture was proved for two special cases, however, for the general case the currently best upper bound is only O(n^{7/4}). This is also the best known bound on the number of tangencies in the relaxed case where every pair of arcs has at most one common point. We improve the bounds for the latter and former cases to O(n^{5/3}) and O(n^{3/2}), respectively. We also consider a few other variants of these questions, for example, we show that if the arcs are x-monotone, each pair intersects at most once and their left endpoints lie on a common vertical line, then the maximum number of tangencies is Θ(n^{4/3}). Without this last condition the number of tangencies is O(n^{4/3}(log n)^{1/3}), improving a previous bound of Pach and Sharir. Along the way we prove a graph-theoretic theorem which extends a result of Erdős and Simonovits and may be of independent interest.
Cite as

Eyal Ackerman and Balázs Keszegh. On the Maximum Number of Tangencies Among 1-Intersecting Curves. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2026.2,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs},
  title =	{{On the Maximum Number of Tangencies Among 1-Intersecting Curves}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{2:1--2: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.2},
  URN =		{urn:nbn:de:0030-drops-258085},
  doi =		{10.4230/LIPIcs.SoCG.2026.2},
  annote =	{Keywords: tangency graph, forbidden subgraph, extremal graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.6
Estimating the Persistent Homology of ℝⁿ-Valued Functions Using Function-Geometric Multifiltrations

Authors: Ethan André, Jingyi Li, David Loiseaux, and Steve Oudot

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

Abstract
Given an unknown ℝⁿ-valued function f on a metric space X, can we approximate the persistent homology of f from a finite sampling of X with known pairwise distances and function values? This question has been answered in the case n = 1, assuming f is Lipschitz continuous and X is a sufficiently regular geodesic metric space, and using filtered geometric complexes with fixed scale parameter for the approximation. In this paper we answer the question for arbitrary n, under similar assumptions and using function-geometric multifiltrations. Our analysis offers a different view on these multifiltrations by focusing on their approximation properties rather than on their stability properties. We also leverage the multiparameter setting to provide insight into the influence of the scale parameter, whose choice is central to this type of approach. From a practical standpoint, we show that our approximation results are robust to input noise, and that function-geometric multifiltrations have good statistical convergence properties. We also provide an algorithm to compute our estimators, and we use its implementation to conduct extensive experiments, on both synthetic and real biological data, in order to validate our theoretical results.
Cite as

Ethan André, Jingyi Li, David Loiseaux, and Steve Oudot. Estimating the Persistent Homology of ℝⁿ-Valued Functions Using Function-Geometric Multifiltrations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andre_et_al:LIPIcs.SoCG.2026.6,
  author =	{Andr\'{e}, Ethan and Li, Jingyi and Loiseaux, David and Oudot, Steve},
  title =	{{Estimating the Persistent Homology of \mathbb{R}ⁿ-Valued Functions Using Function-Geometric Multifiltrations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{6:1--6:18},
  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.6},
  URN =		{urn:nbn:de:0030-drops-258120},
  doi =		{10.4230/LIPIcs.SoCG.2026.6},
  annote =	{Keywords: Topological data analysis, multi-parameter persistent homology, function-Rips multifiltration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.3
Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs

Authors: Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava

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

Abstract
Let G be a finite, connected metric graph and let X be a subset of G. If X is sufficiently dense in G, we show that the Gromov-Hausdorff distance matches the Hausdorff distance, namely d_GH(G,X) = d_H(G,X). When the metric graph is the circle G = S¹ with circumference 2π, a recent study established the equality d_GH(S¹,X) = d_H(S¹,X) whenever d_GH(S¹,X) < π/6. Our results relax this hypothesis to d_GH(S¹,X) < π/3, and furthermore, we show that the constant π/3 is the best possible. We lower bound the Gromov-Hausdorff distance d_GH(G,X) by the Hausdorff distance d_H(G,X) via a simple topological obstruction: the existence of a possibly discontinuous function f: G → X with too small distortion contradicts the connectedness of G.
Cite as

Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava. Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{adams_et_al:LIPIcs.SoCG.2026.3,
  author =	{Adams, Henry and Majhi, Sushovan and Manin, Fedor and Virk, \v{Z}iga and Zava, Nicol\`{o}},
  title =	{{Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{3:1--3:16},
  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.3},
  URN =		{urn:nbn:de:0030-drops-258099},
  doi =		{10.4230/LIPIcs.SoCG.2026.3},
  annote =	{Keywords: Gromov-Hausdorff distance, distortion, connectedness, Borsuk-Ulam theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.22
Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams

Authors: Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani

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

Abstract
In 1984, Winkler conjectured that every simple Venn diagram with n curves can be extended to a simple Venn diagram with n+1 curves. This conjecture is equivalent to the statement that the dual graph of any simple Venn diagram has a Hamilton cycle. In this work, we construct counterexamples to Winkler’s conjecture for all n ≥ 6. As part of this proof, we computed all 3.430.404 simple Venn diagrams with n = 6 curves (even their number was not previously known), among which we found 72 counterexamples. We also disprove another conjecture about the Hamiltonicity of the arrangement graph of a Venn diagram. Specifically, while working on Winkler’s conjecture, Pruesse and Ruskey proved that this graph has a Hamilton cycle for every simple Venn diagram with n curves, and conjectured that this also holds for non-simple diagrams. We construct counterexamples to this conjecture for all n ≥ 4.
Cite as

Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani. Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brenner_et_al:LIPIcs.SoCG.2026.22,
  author =	{Brenner, Sofia and Kleist, Linda and M\"{u}tze, Torsten and Rieck, Christian and Verciani, Francesco},
  title =	{{Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{22:1--22:16},
  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.22},
  URN =		{urn:nbn:de:0030-drops-258285},
  doi =		{10.4230/LIPIcs.SoCG.2026.22},
  annote =	{Keywords: Venn diagram, Winkler’s conjecture, Hamilton cycle, perfect matching, hypercube}
}
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.24
Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support

Authors: Reilly Browne and Hsien-Chih Chang

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

Abstract
Given an unweighted graph G, the minimum r-dominating set problem asks for a subset of vertices S of the smallest cardinality, such that every vertex in G is within radius r to some vertex in S. While the r-dominating set problem on planar graph admits PTAS from Baker’s shifting/layering technique when r is a constant, the problem becomes significantly harder when r can depend on n. In fact, under Exponential-Time Hypothesis, Fox-Epstein ηl [SODA 2019] observed that no efficient PTAS can exist for the unbounded r-dominating set problem on planar graphs. One may consider even harder weighted-variant known as the vertex-weighted metric r-dominating set, where edges are associated with lengths, and every vertex is associated with a positive-valued weight, and the goal is to compute an r-dominating set with minimum total weight. As a result, people resorted to bicriteria algorithms by allowing the returned solution to use radius-(1+ε)r balls instead, in addition to the total weight being a 1+ε approximation to the optimal value. We establish the first single-criteria polynomial-time O(1)-approximation algorithm for the vertex-weighted metric r-dominating set problem on planar graphs when r is part of the input, and can be arbitrarily large compared to n. Our new (single-criteria) O(1)-approximation algorithm uses the quasi-uniformity sampling technique of Chan et al. [SODA 2012] by bounding the shallow cell complexity of the (unbounded) radius-r ball system to be linear in n. To this end we have two technical innovations: 1) The discrete ball system on planar graphs are neither pseudodisks nor have well-defined boundaries for standard union-complexity arguments. We construct a support graph for arbitrary distance ball systems as contractions of Voronoi cells; the sparseness comes as a byproduct. 2) We present an assignment of each depth-(≥3) cell to a unique 3-tuple of ball centers. This allows us to use standard Clarkson-Shor techniques to reduce the counting to cells of depth exactly 3, which we prove to be size O(n) by a novel geometric argument based on our support being a Voronoi contraction.
Cite as

Reilly Browne and Hsien-Chih Chang. Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{browne_et_al:LIPIcs.SoCG.2026.24,
  author =	{Browne, Reilly and Chang, Hsien-Chih},
  title =	{{Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{24:1--24:17},
  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.24},
  URN =		{urn:nbn:de:0030-drops-258300},
  doi =		{10.4230/LIPIcs.SoCG.2026.24},
  annote =	{Keywords: Minimum dominating set, planar graphs, shallow cell complexity}
}
  • Refine by Type
  • 232 Document/PDF
  • 136 Document/HTML
  • 2 Volume

  • Refine by Publication Year
  • 117 2026
  • 22 2025
  • 2 2022
  • 78 2021
  • 1 2019
  • Show More...

  • Refine by Author
  • 25 Ahn, Hee-Kap
  • 16 Oh, Eunjin
  • 6 Bhore, Sujoy
  • 6 Fekete, Sándor P.
  • 5 Chan, Timothy M.
  • Show More...

  • Refine by Series/Journal
  • 231 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 114 Theory of computation → Computational geometry
  • 22 Theory of computation → Design and analysis of algorithms
  • 15 Mathematics of computing → Graph algorithms
  • 15 Theory of computation → Approximation algorithms analysis
  • 12 Mathematics of computing → Algebraic topology
  • Show More...

  • Refine by Keyword
  • 7 approximation algorithms
  • 6 Topological Data Analysis
  • 6 computational geometry
  • 5 Computational Geometry
  • 5 geodesic distance
  • 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