Search Results

Documents authored by Rehs, Carolin

Document
DOI: 10.4230/LIPIcs.ESA.2026.102
On Small Pair Decompositions for Point Sets

Authors: Kevin Buchin, Jacobus Conradi, Sariel Har-Peled, Antonia Kalb, Abhiruk Lahiri, Lukas Plätz, Carolin Rehs, and Sampson Wong

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We study the problem of computing a minimum-size Well-Separated Pair Decomposition (WSPD) of a given point set. We obtain the following results for the minimum-size WSPD: (1) a constant-factor approximation in doubling metrics, (2) a simple 3-approximation in ℝ, and (3) an NP-hardness proof in ℝ². We also provide an optimal output-sensitive runtime for the algorithm in doubling metrics and an implementation of the 3-approximation algorithm in ℝ. Furthermore, we introduce a new pair-decomposition for point sets in a metric space. It is defined using a relaxed requirement that, for all pairs {X,Y} in the decomposition, all the distances of pairs of points in X × Y are equal up to a factor in [1 ± ε]. Surprisingly, we show that in a general metric space, one can compute such a decomposition of size O(n/ε log n), which is dramatically smaller than the Θ(n²) bound for WSPDs. For a point set in ℝ^d, the bound improves to O(d n/ε log 1/ε).
Cite as

Kevin Buchin, Jacobus Conradi, Sariel Har-Peled, Antonia Kalb, Abhiruk Lahiri, Lukas Plätz, Carolin Rehs, and Sampson Wong. On Small Pair Decompositions for Point Sets. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 102:1-102:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2026.102,
  author =	{Buchin, Kevin and Conradi, Jacobus and Har-Peled, Sariel and Kalb, Antonia and Lahiri, Abhiruk and Pl\"{a}tz, Lukas and Rehs, Carolin and Wong, Sampson},
  title =	{{On Small Pair Decompositions for Point Sets}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{102:1--102:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.102},
  URN =		{urn:nbn:de:0030-drops-272380},
  doi =		{10.4230/LIPIcs.ESA.2026.102},
  annote =	{Keywords: Well-separated pair decomposition, Semi-separated pair decomposition, Approximation algorithms, Doubling metrics, Computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.117
Sparse Oriented Spanners in Metric Spaces

Authors: Sujoy Bhore, Ahmad Biniaz, Kevin Buchin, Jean-Lou De Carufel, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, and Michiel Smid

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Oriented spanners were presented at ESA'23 as an extension of the well-researched geometric spanners: Given a set P of points in a metric space and an oriented graph G, the oriented dilation of two points p,q ∈ P is the length of the shortest closed walk in G containing p and q divided by the minimum perimeter triangle of p and q. G is called a t-spanner, if the maximum dilation over all pairs of points in P is at most t. This paper presents the first constructions of sparse oriented spanners for metric spaces beyond the Euclidean space. Given an orientation of the complete graph (i.e. a tournament) with dilation t on n points that satisfies an additional short-cycle property, we show how to extract a (t+ε)-spanner with 𝒪(k) edges in 𝒪(kn²+T(n)) time, for any metric space admitting a well-separated pair decomposition with k pairs computable in T(n) time. We supplement this with an improved construction of tournaments for metric point sets, obtaining dilation 5/3. This improves the previous bound of 2 and approaches the lower bound of 1.5. Combined, for n points in a metric space with constant doubling dimension d, this yields a (5/3 + ε)-spanner with (1/ε)^{𝒪(d)}n edges computable in (1/ε)^𝒪(d) n³ time using 𝒪(n²) space. This improves the dilation over the (2+ε)-spanner for Euclidean point sets presented at SoCG’25 while applying to more general metric spaces. Moreover, we generalize the known (2+ε)-spanner to doubling spaces. In particular, an oriented (2+ε)-spanner with 𝒪(ε^{-d} n) edges can be constructed in (1/ε)^𝒪(d) n log n time using 𝒪(ε^{-d} n) space. Since the oriented dilation can be dominated by one pair of points, we also consider the oriented average dilation, which is the sum over the oriented dilation of all pairs of points divided by the number of pairs. While oriented (1+ε)-spanners do not exist for every point set, we present an algorithm that computes a spanner with average dilation 1+ε for point sets in a metric space of constant doubling dimension d: More concretely, our algorithm computes an oriented spanner with average dilation at most 1 + 𝒪(1/s) + s^𝒪(d)/n with s^𝒪(d) n edges in s^𝒪(d) n log n time using s^𝒪(d) n space, where s is any sufficiently large number that may depend on n.
Cite as

Sujoy Bhore, Ahmad Biniaz, Kevin Buchin, Jean-Lou De Carufel, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, and Michiel Smid. Sparse Oriented Spanners in Metric Spaces. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 117:1-117:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ESA.2026.117,
  author =	{Bhore, Sujoy and Biniaz, Ahmad and Buchin, Kevin and De Carufel, Jean-Lou and Kalb, Antonia and Maheshwari, Anil and Odak, Saeed and Rehs, Carolin and Smid, Michiel},
  title =	{{Sparse Oriented Spanners in Metric Spaces}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{117:1--117:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.117},
  URN =		{urn:nbn:de:0030-drops-272532},
  doi =		{10.4230/LIPIcs.ESA.2026.117},
  annote =	{Keywords: spanner, oriented graph, dilation, doubling dimension, orientation, tournament, well-separated pair decomposition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.26
Geometric Spanners of Bounded Tree-Width

Authors: Kevin Buchin, Carolin Rehs, and Torben Scheele

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

Abstract
Given a point set P in the Euclidean space, a geometric t-spanner G is a graph on P such that for every pair of points, the shortest path in G between those points is at most a factor t longer than the Euclidean distance between those points. The value t ≥ 1 is called the dilation of G. Commonly, the aim is to construct a t-spanner with additional desirable properties. In graph theory, a powerful tool to admit efficient algorithms is bounded tree-width. We therefore investigate the problem of computing geometric spanners with bounded tree-width and small dilation t. Let d be a fixed integer and P ⊂ ℝ^d be a point set with n points. We give a first algorithm to compute an 𝒪(n/k^{d/(d-1)})-spanner on P with tree-width at most k. The dilation obtained by the algorithm is asymptotically worst-case optimal for graphs with tree-width k: We show that there is a set of n points such that every spanner of tree-width k has dilation 𝒪(n/k^{d/(d-1)}). We further prove a tight dependency between tree-width and the number of edges in sparse connected planar graphs, which admits, for point sets in ℝ², a plane spanner with tree-width at most k and small maximum vertex degree. Finally, we show an almost tight bound on the minimum dilation of a spanning tree of n equally spaced points on a circle.
Cite as

Kevin Buchin, Carolin Rehs, and Torben Scheele. Geometric Spanners of Bounded Tree-Width. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2025.26,
  author =	{Buchin, Kevin and Rehs, Carolin and Scheele, Torben},
  title =	{{Geometric Spanners of Bounded Tree-Width}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.26},
  URN =		{urn:nbn:de:0030-drops-231786},
  doi =		{10.4230/LIPIcs.SoCG.2025.26},
  annote =	{Keywords: Computational Geometry, Geometric Spanner, Tree-width}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.27
Computing Oriented Spanners and Their Dilation

Authors: Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong

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

Abstract
Given a point set P in a metric space and a real number t ≥ 1, an oriented t-spanner is an oriented graph G = (P, E), where for every pair of distinct points p and q in P, the shortest oriented closed walk in G that contains p and q is at most a factor t longer than the perimeter of the smallest triangle in P containing p and q. The oriented dilation of a graph G is the minimum t for which G is an oriented t-spanner. For arbitrary point sets of size n in ℝ^d, where d ≥ 2 is a constant, the only known oriented spanner construction is an oriented 2-spanner with binom(n,2) edges. Moreover, there exists a set P of four points in the plane, for which the oriented dilation is larger than 1.46, for any oriented graph on P. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of n points in ℝ^d, where d is a constant, we construct an oriented (2+ε)-spanner with 𝒪(n) edges in 𝒪(n log n) time and 𝒪(n) space. Our construction uses the well-separated pair decomposition and an algorithm that computes a (1+ε)-approximation of the minimum-perimeter triangle in P containing two given query points in 𝒪(log n) time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the oriented graph is already given, computing its oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in ℝ^d, where d is a constant.
Cite as

Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong. Computing Oriented Spanners and Their Dilation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2025.27,
  author =	{Buchin, Kevin and Kalb, Antonia and Maheshwari, Anil and Odak, Saeed and Rehs, Carolin and Smid, Michiel and Wong, Sampson},
  title =	{{Computing Oriented Spanners and Their Dilation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.27},
  URN =		{urn:nbn:de:0030-drops-231792},
  doi =		{10.4230/LIPIcs.SoCG.2025.27},
  annote =	{Keywords: spanner, oriented graph, dilation, orientation, well-separated pair decomposition, minimum-perimeter triangle}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.26
Oriented Spanners

Authors: Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in 𝒪(n⁸) time for n points, and a greedy algorithm that computes a 5-spanner in 𝒪(nlog n) time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented 𝒪(1)-spanner.
Cite as

Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov, Carolin Rehs, André van Renssen, and Sampson Wong. Oriented Spanners. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2023.26,
  author =	{Buchin, Kevin and Gudmundsson, Joachim and Kalb, Antonia and Popov, Aleksandr and Rehs, Carolin and van Renssen, Andr\'{e} and Wong, Sampson},
  title =	{{Oriented Spanners}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.26},
  URN =		{urn:nbn:de:0030-drops-186796},
  doi =		{10.4230/LIPIcs.ESA.2023.26},
  annote =	{Keywords: computational geometry, spanner, oriented graph, greedy triangulation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.71
A Timecop’s Work Is Harder Than You Think

Authors: Nils Morawietz, Carolin Rehs, and Mathias Weller

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We consider the (parameterized) complexity of a cop and robber game on periodic, temporal graphs and a problem on periodic sequences to which these games relate intimately. In particular, we show that it is NP-hard to decide (a) whether there is some common index at which all given periodic, binary sequences are 0, and (b) whether a single cop can catch a single robber on an edge-periodic temporal graph. We further present results for various parameterizations of both problems and show that hardness not only applies in general, but also for highly limited instances. As one main result we show that even if the graph has a size-2 vertex cover and is acyclic in each time step, the cop and robber game on periodic, temporal graphs is NP-hard and W[1]-hard when parameterized by the size of the underlying input graph.
Cite as

Nils Morawietz, Carolin Rehs, and Mathias Weller. A Timecop’s Work Is Harder Than You Think. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{morawietz_et_al:LIPIcs.MFCS.2020.71,
  author =	{Morawietz, Nils and Rehs, Carolin and Weller, Mathias},
  title =	{{A Timecop’s Work Is Harder Than You Think}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.71},
  URN =		{urn:nbn:de:0030-drops-127404},
  doi =		{10.4230/LIPIcs.MFCS.2020.71},
  annote =	{Keywords: edge-periodic temporal graphs, cops and robbers, tally-intersection, congruence satisfyability}
}

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