7 Search Results for "van de Kerkhof, Mees"

Document
DOI: 10.4230/LIPIcs.SEA.2026.1
Global Polyline Simplification Under the Fréchet Distance: Theory and Practice

Authors: Christian Abdullahad and Sabine Storandt

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Given an input polyline with n vertices, the global polyline simplification problem seeks a simplified polyline with the minimum number of vertices whose distance to the original polyline does not exceed a given bound. For the vertex-restricted variant, where the simplified polyline is required to be a subsequence of the input vertices, an algorithm with a running time of 𝒪(n³) was presented in previous work, using the Fréchet distance as the polyline similarity measure. A closely related variant is the local polyline simplification problem, in which the distance bound is required to hold for every individual shortcut segment replacing a sub-polyline. This condition implies that any locally valid simplification is also globally valid, whereas the converse does not hold. As a consequence, globally optimal simplifications may use substantially fewer vertices than locally optimal ones. Indeed, in previous work, instances were constructed in which the optimal global simplification is smaller by a constant factor. On the algorithmic side, optimal local simplifications can be computed significantly faster, namely in 𝒪(n² log n) under the Fréchet distance, and efficient heuristics are also available. This raises the question of which problem variant is more suitable for practical application. In this paper, we first show that there exist instances for which the optimal solution sizes of global and local polyline simplification differ by a factor in Θ(n), substantially strengthening the previously known constant-factor separation. We then present the first practical implementations of existing algorithms for global polyline simplification and experimentally evaluate their performance. To this end, we introduce several engineering techniques that considerably accelerate these algorithms. Moreover, we develop an implicit Fréchet framework that allows many Fréchet-related problems to be addressed in a weaker computational model. Within this framework, explicit geometric computations can be reduced to simple comparisons, resulting in significantly more robust implementations. Somewhat surprisingly, our experimental results reveal that, despite the large worst-case gap established by our theoretical result, the difference in solution size between optimal global and local simplifications is negligible in practice. Motivated by this observation, we propose a heuristic for global polyline simplification that is guaranteed to produce solutions of size equal to or smaller than the optimal local simplification. On a benchmark consisting of one million polylines, the heuristic yields suboptimal results on only eight while being significantly faster than the optimal algorithms.
Cite as

Christian Abdullahad and Sabine Storandt. Global Polyline Simplification Under the Fréchet Distance: Theory and Practice. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abdullahad_et_al:LIPIcs.SEA.2026.1,
  author =	{Abdullahad, Christian and Storandt, Sabine},
  title =	{{Global Polyline Simplification Under the Fr\'{e}chet Distance: Theory and Practice}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.1},
  URN =		{urn:nbn:de:0030-drops-260055},
  doi =		{10.4230/LIPIcs.SEA.2026.1},
  annote =	{Keywords: Polyline Simplification, Shortcut Graph, Fr\'{e}chet Distance}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.6
A Dimension-Reducing Fréchet Simplification Oracle

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh

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

Abstract
Let P be a polygonal curve with n vertices in the plane. We construct a data structure of size O(n log n) suited for simplification queries of the following kind. Given a query line 𝓁 and an integer k ≥ 1, find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to P, among all such curves. Using our data structure, a query can be handled in O(k² log³ n + k log⁴n) time. More generally, a geometric tree T on n vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair u, v of its vertices, a line 𝓁, and an integer k ≥ 1, one can find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to the path from u to v in T, in time O(k² polylog n). For the general dimension-reduction problem, where P is a curve in ℝ^d (d ≥ 3), 0 < ε₀ < 1 is a real parameter, and a query specifies a g-flat h (1 ≤ g ≤ d-1) and an integer k ≥ 1, we construct a data structure of size O(nlog n + f(ε₀) n), where f(ε₀) = (1+1/ε₀)^{(d-1)/2}, that allows us to find a curve Q on h with at most k vertices, whose discrete Fréchet distance to P is at most 1+ε₀ times the distance of Q^* to P, where Q^* is such a curve that minimizes the distance to P. The query handling time is O(f(ε₀) k² log² n).
Cite as

Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. A Dimension-Reducing Fréchet Simplification Oracle. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2025.6,
  author =	{Aronov, Boris and Farhana, Tsuri and Katz, Matthew J. and Ramesh, Indu},
  title =	{{A Dimension-Reducing Fr\'{e}chet Simplification Oracle}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{6:1--6:20},
  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.6},
  URN =		{urn:nbn:de:0030-drops-249149},
  doi =		{10.4230/LIPIcs.ISAAC.2025.6},
  annote =	{Keywords: Computational geometry, discrete Fr\'{e}chet distance, curve simplification oracle, restricted minimum enclosing disk queries}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.36
Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

Authors: Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf

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

Abstract
We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).
Cite as

Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf. Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brunck_et_al:LIPIcs.GD.2025.36,
  author =	{Brunck, Florestan and Chang, Hsien-Chih and L\"{o}ffler, Maarten and Ophelders, Tim and Schlipf, Lena},
  title =	{{Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{36:1--36:18},
  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.36},
  URN =		{urn:nbn:de:0030-drops-250220},
  doi =		{10.4230/LIPIcs.GD.2025.36},
  annote =	{Keywords: Curve Arrangements, Reconfiguration, Curve Arrangements, NP-hardness, Fixed-Parameter Tractability, Puzzle Generation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.133
Faster, Deterministic and Space Efficient Subtrajectory Clustering

Authors: Ivor van der Hoog, Thijs van der Horst, and Tim Ophelders

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given a trajectory T and a distance Δ, we wish to find a set C of curves of complexity at most 𝓁, such that we can cover T with subcurves that each are within Fréchet distance Δ to at least one curve in C. We call C an (𝓁,Δ)-clustering and aim to find an (𝓁,Δ)-clustering of minimum cardinality. This problem variant was introduced by Akitaya et al. (2021) and shown to be NP-complete. The main focus has therefore been on bicriteria approximation algorithms, allowing for the clustering to be an (𝓁, Θ(Δ))-clustering of roughly optimal size. We present algorithms that construct (𝓁,4Δ)-clusterings of 𝒪(k log n) size, where k is the size of the optimal (𝓁, Δ)-clustering. We use 𝒪(n³) space and 𝒪(k n³ log⁴ n) time. Our algorithms significantly improve upon the clustering quality (improving the approximation factor in Δ) and size (whenever 𝓁 ∈ Ω(log n / log k)). We offer deterministic running times improving known expected bounds by a factor near-linear in 𝓁. Additionally, we match the space usage of prior work, and improve it substantially, by a factor super-linear in n𝓁, when compared to deterministic results.
Cite as

Ivor van der Hoog, Thijs van der Horst, and Tim Ophelders. Faster, Deterministic and Space Efficient Subtrajectory Clustering. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 133:1-133:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ICALP.2025.133,
  author =	{van der Hoog, Ivor and van der Horst, Thijs and Ophelders, Tim},
  title =	{{Faster, Deterministic and Space Efficient Subtrajectory Clustering}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{133:1--133:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.133},
  URN =		{urn:nbn:de:0030-drops-235109},
  doi =		{10.4230/LIPIcs.ICALP.2025.133},
  annote =	{Keywords: Fr\'{e}chet distance, clustering, set cover}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.36
Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.
Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.67
Global Curve Simplification

Authors: Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Due to its many applications, curve simplification is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve P with n vertices, the goal is to find another polygonal curve P' with a smaller number of vertices such that P' is sufficiently similar to P. Quality guarantees of a simplification are usually given in a local sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work we aim to provide a systematic overview of curve simplification problems under global distance measures that bound the distance between P and P'. We consider six different curve distance measures: three variants of the Hausdorff distance and three variants of the Fréchet distance. And we study different restrictions on the choice of vertices for P'. We provide polynomial-time algorithms for some variants of the global curve simplification problem, and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.
Cite as

Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk. Global Curve Simplification. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vandekerkhof_et_al:LIPIcs.ESA.2019.67,
  author =	{van de Kerkhof, Mees and Kostitsyna, Irina and L\"{o}ffler, Maarten and Mirzanezhad, Majid and Wenk, Carola},
  title =	{{Global Curve Simplification}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.67},
  URN =		{urn:nbn:de:0030-drops-111887},
  doi =		{10.4230/LIPIcs.ESA.2019.67},
  annote =	{Keywords: Curve simplification, Fr\'{e}chet distance, Hausdorff distance}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.52
Convex Partial Transversals of Planar Regions

Authors: Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.
Cite as

Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex Partial Transversals of Planar Regions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{keikha_et_al:LIPIcs.ISAAC.2018.52,
  author =	{Keikha, Vahideh and van de Kerkhof, Mees and van Kreveld, Marc and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi L. and Wiratma, Lionov},
  title =	{{Convex Partial Transversals of Planar Regions}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.52},
  URN =		{urn:nbn:de:0030-drops-100003},
  doi =		{10.4230/LIPIcs.ISAAC.2018.52},
  annote =	{Keywords: computational geometry, algorithms, NP-hardness, convex transversals}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 1 2019
  • 1 2018

  • Refine by Author
  • 3 Löffler, Maarten
  • 2 Kostitsyna, Irina
  • 2 Ophelders, Tim
  • 2 van de Kerkhof, Mees
  • 1 Abdullahad, Christian
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 7 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 3 Fréchet distance
  • 2 NP-hardness
  • 1 Computational geometry
  • 1 Curve Arrangements
  • 1 Curve simplification
  • 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