Search Results

Documents authored by Kolbe, Benedikt

Artifact
Software
DOI: 10.4230/artifacts.23288
nonObtuseTri

Authors: Mikkel Abrahamsen, Florestan Brunck, Jacobus Conradi, Benedikt Kolbe, and André Nusser

Abstract
Cite as

Mikkel Abrahamsen, Florestan Brunck, Jacobus Conradi, Benedikt Kolbe, André Nusser. nonObtuseTri (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23288,
   title = {{nonObtuseTri}}, 
   author = {Abrahamsen, Mikkel and Brunck, Florestan and Conradi, Jacobus and Kolbe, Benedikt and Nusser, Andr\'{e}},
   note = {Software, version v3.0., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:b6301970ab626c084f309f9b5e6b91e9acf24949;origin=https://github.com/JacobusTheSecond/nonObtuseTri;visit=swh:1:snp:4b7f079e3cd897cb0826392670078921ce262ba2;anchor=swh:1:rev:bd1842a4272b4e01ad623cf6bb02c7617c3da98a}{\texttt{swh:1:dir:b6301970ab626c084f309f9b5e6b91e9acf24949}} (visited on 2025-06-20)},
   url = {https://github.com/JacobusTheSecond/nonObtuseTri},
   doi = {10.4230/artifacts.23288},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.22
Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D

Authors: Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, and Marena Richter

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

Abstract
The Fréchet distance is a computational mainstay for comparing polygonal curves. The Fréchet distance under translation, which is a translation invariant version, considers the similarity of two curves independent of their location in space. It is defined as the minimum Fréchet distance that arises from allowing arbitrary translations of the input curves. This problem and numerous variants of the Fréchet distance under some transformations have been studied, with more work concentrating on the discrete Fréchet distance, leaving a significant gap between the discrete and continuous versions of the Fréchet distance under transformations. Our contribution is twofold: First, we present an algorithm for the Fréchet distance under translation on 1-dimensional curves of complexity n with a running time of 𝒪(n^{8/3} log³ n). To achieve this, we develop a novel framework for the problem for 1-dimensional curves, which also applies to other scenarios and leads to our second contribution. We present an algorithm with the same running time of 𝒪(n^{8/3} log³ n) for the Fréchet distance under scaling for 1-dimensional curves. For both algorithms we match the running times of the discrete case and improve the previously best known bounds of 𝒪̃(n⁴). Our algorithms rely on technical insights but are conceptually simple, essentially reducing the continuous problem to the discrete case across different length scales.
Cite as

Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, and Marena Richter. Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.SoCG.2025.22,
  author =	{Blank, Lotte and Conradi, Jacobus and Driemel, Anne and Kolbe, Benedikt and Nusser, Andr\'{e} and Richter, Marena},
  title =	{{Transforming Dogs on the Line: On the Fr\'{e}chet Distance Under Translation or Scaling in 1D}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{22:1--22:16},
  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.22},
  URN =		{urn:nbn:de:0030-drops-231746},
  doi =		{10.4230/LIPIcs.SoCG.2025.22},
  annote =	{Keywords: Fr\'{e}chet distance under translation, Fr\'{e}chet distance under scaling, time series, shape matching}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2025.79
Computing Non-Obtuse Triangulations with Few Steiner Points (CG Challenge)

Authors: Mikkel Abrahamsen, Florestan Brunck, Jacobus Conradi, Benedikt Kolbe, and André Nusser

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

Abstract
We present the winning implementation of the Seventh Computational Geometry Challenge (CG:SHOP 2025). The task in this challenge was to find non-obtuse triangulations for given planar regions, respecting a given set of constraints consisting of extra vertices and edges that must be part of the triangulation. The goal was to minimize the number of introduced Steiner points. Our approach is to maintain a constrained Delaunay triangulation, for which we repeatedly remove, relocate, or add Steiner points. We use local search to choose the action that improves the triangulation the most, until the resulting triangulation is non-obtuse.
Cite as

Mikkel Abrahamsen, Florestan Brunck, Jacobus Conradi, Benedikt Kolbe, and André Nusser. Computing Non-Obtuse Triangulations with Few Steiner Points (CG Challenge). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2025.79,
  author =	{Abrahamsen, Mikkel and Brunck, Florestan and Conradi, Jacobus and Kolbe, Benedikt and Nusser, Andr\'{e}},
  title =	{{Computing Non-Obtuse Triangulations with Few Steiner Points}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{79:1--79:13},
  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.79},
  URN =		{urn:nbn:de:0030-drops-232311},
  doi =		{10.4230/LIPIcs.SoCG.2025.79},
  annote =	{Keywords: non-obtuse triangulation, local search, competition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.42
Fast Approximations and Coresets for (k,𝓁)-Median Under Dynamic Time Warping

Authors: Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde

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

Abstract
We present algorithms for the computation of ε-coresets for k-median clustering of point sequences in ℝ^d under the p-dynamic time warping (DTW) distance. Coresets under DTW have not been investigated before, and the analysis is not directly accessible to existing methods as DTW is not a metric. The three main ingredients that allow our construction of coresets are the adaptation of the ε-coreset framework of sensitivity sampling, bounds on the VC dimension of approximations to the range spaces of balls under DTW, and new approximation algorithms for the k-median problem under DTW. We achieve our results by investigating approximations of DTW that provide a trade-off between the provided accuracy and amenability to known techniques. In particular, we observe that given n curves under DTW, one can directly construct a metric that approximates DTW on this set, permitting the use of the wealth of results on metric spaces for clustering purposes. The resulting approximations are the first with polynomial running time and achieve a very similar approximation factor as state-of-the-art techniques. We apply our results to produce a practical algorithm approximating (k,𝓁)-median clustering under DTW.
Cite as

Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde. Fast Approximations and Coresets for (k,𝓁)-Median Under Dynamic Time Warping. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.SoCG.2024.42,
  author =	{Conradi, Jacobus and Kolbe, Benedikt and Psarros, Ioannis and Rohde, Dennis},
  title =	{{Fast Approximations and Coresets for (k,𝓁)-Median Under Dynamic Time Warping}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.42},
  URN =		{urn:nbn:de:0030-drops-199875},
  doi =		{10.4230/LIPIcs.SoCG.2024.42},
  annote =	{Keywords: Dynamic time warping, coreset, median clustering, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.27
Computing a Dirichlet Domain for a Hyperbolic Surface

Authors: Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud

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

Abstract
This paper exhibits and analyzes an algorithm that takes a given closed orientable hyperbolic surface and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While grounded in topological considerations, the algorithm makes key use of the geometry of the surface. We introduce data structures that reflect this interplay between geometry and topology and show that the algorithm runs in polynomial time, in terms of the initial perimeter and the genus of the surface.
Cite as

Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud. Computing a Dirichlet Domain for a Hyperbolic Surface. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{despre_et_al:LIPIcs.SoCG.2023.27,
  author =	{Despr\'{e}, Vincent and Kolbe, Benedikt and Parlier, Hugo and Teillaud, Monique},
  title =	{{Computing a Dirichlet Domain for a Hyperbolic Surface}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.27},
  URN =		{urn:nbn:de:0030-drops-178771},
  doi =		{10.4230/LIPIcs.SoCG.2023.27},
  annote =	{Keywords: Hyperbolic geometry, Topology, Voronoi diagram, Algorithm}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact