Search Results

Documents authored by van der Horst, Thijs

Document
DOI: 10.4230/LIPIcs.ESA.2025.24
Fréchet Distance in Unweighted Planar Graphs

Authors: Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg, and Lasse Wulf

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

Abstract
The Fréchet distance is a distance measure between trajectories in ℝ^d or walks in a graph G. Given constant-time shortest path queries, the Discrete Fréchet distance D_G(P, Q) between two walks P and Q can be computed in O(|P|⋅|Q|) time using a dynamic program. Driemel, van der Hoog, and Rotenberg [SoCG'22] show that for weighted planar graphs this approach is likely tight, as there can be no strongly-subquadratic algorithm to compute a 1.01-approximation of D_G(P, Q) unless the Orthogonal Vector Hypothesis (OVH) fails. Such quadratic-time conditional lower bounds are common to many Fréchet distance variants. However, they can be circumvented by assuming that the input comes from some well-behaved class: There exist (1+ε)-approximations, both in weighted graphs and in ℝ^d, that take near-linear time for c-packed or κ-straight walks in the graph. In ℝ^d there also exists a near-linear time algorithm to compute the Fréchet distance whenever all input edges are long compared to the distance. We consider computing the Fréchet distance in unweighted planar graphs. We show that there exist no strongly-subquadratic 1.25-approximations of the discrete Fréchet distance between two disjoint simple paths in an unweighted planar graph in strongly subquadratic time, unless OVH fails. This improves the previous lower bound, both in terms of generality and approximation factor. We subsequently show that adding graph structure circumvents this lower bound: If the graph is a regular tiling with unit-weighted edges, then there exists an Õ((|P|+|Q|)^{1.5})-time algorithm to compute D_G(P, Q). Our result has natural implications in the plane, as it allows us to define a new class of well-behaved curves that facilitate (1+ε)-approximations of their discrete Fréchet distance in subquadratic time.
Cite as

Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg, and Lasse Wulf. Fréchet Distance in Unweighted Planar Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ESA.2025.24,
  author =	{van der Hoog, Ivor and van der Horst, Thijs and Rotenberg, Eva and Wulf, Lasse},
  title =	{{Fr\'{e}chet Distance in Unweighted Planar Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-244924},
  doi =		{10.4230/LIPIcs.ESA.2025.24},
  annote =	{Keywords: Fr\'{e}chet distance, planar graphs, lower bounds, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.35
The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon

Authors: Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann

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

Abstract
The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in ℝ^d: near-quadratic time algorithms exist, and conditional lower bounds suggest that these results cannot be improved significantly, even in one dimension and when approximating with a factor less than three. We consider the special case where the curves bound a simple polygon and distances are measured via geodesics inside this simple polygon. Here the conditional lower bounds do not apply; Efrat et al. (2002) were able to give a near-linear time 2-approximation algorithm. In this paper, we significantly improve upon their result: we present a (1+ε)-approximation algorithm, for any ε > 0, that runs in 𝒪(1/(ε) (n+m log n) log nm log 1/(ε)) time for a simple polygon bounded by two curves with n and m vertices, respectively. To do so, we show how to compute the reachability of specific groups of points in the free space at once, by interpreting the free space as one between separated one-dimensional curves. We solve this one-dimensional problem in near-linear time, generalizing a result by Bringmann and Künnemann (2015). Finally, we give a linear time exact algorithm if the two curves bound a convex polygon.
Cite as

Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann. The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.ESA.2025.35,
  author =	{van der Horst, Thijs and van Kreveld, Marc and Ophelders, Tim and Speckmann, Bettina},
  title =	{{The Geodesic Fr\'{e}chet Distance Between Two Curves Bounding a Simple Polygon}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{35:1--35: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.35},
  URN =		{urn:nbn:de:0030-drops-245038},
  doi =		{10.4230/LIPIcs.ESA.2025.35},
  annote =	{Keywords: Fr\'{e}chet distance, approximation, geodesic, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.37
A Near-Linear Time Exact Algorithm for the L₁-Geodesic Fréchet Distance Between Two Curves on the Boundary of a Simple Polygon

Authors: Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann

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

Abstract
Let P be a polygon with k vertices. Let R and B be two simple, interior disjoint curves on the boundary of P, with n and m vertices. We show how to compute the Fréchet distance between R and B using the geodesic L₁-distance in P in 𝒪(k log nm + (n+m) (log² nm log k + log⁴ nm)) time.
Cite as

Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann. A Near-Linear Time Exact Algorithm for the L₁-Geodesic Fréchet Distance Between Two Curves on the Boundary of a Simple Polygon. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.WADS.2025.37,
  author =	{van der Horst, Thijs and van Kreveld, Marc and Ophelders, Tim and Speckmann, Bettina},
  title =	{{A Near-Linear Time Exact Algorithm for the L₁-Geodesic Fr\'{e}chet Distance Between Two Curves on the Boundary of a Simple Polygon}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{37:1--37:13},
  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.37},
  URN =		{urn:nbn:de:0030-drops-242681},
  doi =		{10.4230/LIPIcs.WADS.2025.37},
  annote =	{Keywords: Fr\'{e}chet distance, geodesic, simple polygon}
}
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
DOI: 10.4230/LIPIcs.ISAAC.2024.33
Robust Bichromatic Classification Using Two Lines

Authors: Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Given two sets R and B of n points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the "red" points in R from the "blue" points in B and is robust to outliers. More precisely, we find a region 𝒲_B bounded by two lines, so either a halfplane, strip, wedge, or double wedge, containing (most of) the blue points B, and few red points. Our running times vary between optimal O(nlog n) up to around O(n³), depending on the type of region 𝒲_B and whether we wish to minimize only red outliers, only blue outliers, or both.
Cite as

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals. Robust Bichromatic Classification Using Two Lines. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{glazenburg_et_al:LIPIcs.ISAAC.2024.33,
  author =	{Glazenburg, Erwin and van der Horst, Thijs and Peters, Tom and Speckmann, Bettina and Staals, Frank},
  title =	{{Robust Bichromatic Classification Using Two Lines}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.33},
  URN =		{urn:nbn:de:0030-drops-221605},
  doi =		{10.4230/LIPIcs.ISAAC.2024.33},
  annote =	{Keywords: Geometric Algorithms, Separating Line, Classification, Bichromatic, Duality}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.63
Faster Fréchet Distance Approximation Through Truncated Smoothing

Authors: Thijs van der Horst and Tim Ophelders

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

Abstract
The Fréchet distance is a popular distance measure for curves. Computing the Fréchet distance between two polygonal curves of n vertices takes roughly quadratic time, and conditional lower bounds suggest that even approximating to within a factor 3 cannot be done in strongly-subquadratic time, even in one dimension. The current best approximation algorithms present trade-offs between approximation quality and running time. Recently, van der Horst et al. (SODA, 2023) presented an O((n²/α) log³ n) time α-approximate algorithm for curves in arbitrary dimensions, for any α ∈ [1, n]. Our main contribution is an approximation algorithm for curves in one dimension, with a significantly faster running time of O(n log³ n + (n²/α³) log²n log log n). Additionally, we give an algorithm for curves in arbitrary dimensions that improves upon the state-of-the-art running time by a logarithmic factor, to O((n²/α) log² n). Both of our algorithms rely on a linear-time simplification procedure that in one dimension reduces the complexity of the reachable free space to O(n²/α) without making sacrifices in the asymptotic approximation factor.
Cite as

Thijs van der Horst and Tim Ophelders. Faster Fréchet Distance Approximation Through Truncated Smoothing. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.SoCG.2024.63,
  author =	{van der Horst, Thijs and Ophelders, Tim},
  title =	{{Faster Fr\'{e}chet Distance Approximation Through Truncated Smoothing}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{63:1--63:15},
  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.63},
  URN =		{urn:nbn:de:0030-drops-200083},
  doi =		{10.4230/LIPIcs.SoCG.2024.63},
  annote =	{Keywords: Fr\'{e}cht distance, approximation algorithms, simplification}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.67
Chromatic k-Nearest Neighbor Queries

Authors: Thijs van der Horst, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Let P be a set of n colored points. We develop efficient data structures that store P and can answer chromatic k-nearest neighbor (k-NN) queries. Such a query consists of a query point q and a number k, and asks for the color that appears most frequently among the k points in P closest to q. Answering such queries efficiently is the key to obtain fast k-NN classifiers. Our main aim is to obtain query times that are independent of k while using near-linear space. We show that this is possible using a combination of two data structures. The first data structure allow us to compute a region containing exactly the k-nearest neighbors of a query point q, and the second data structure can then report the most frequent color in such a region. This leads to linear space data structures with query times of O(n^{1/2} log n) for points in ℝ¹, and with query times varying between O(n^{2/3}log^{2/3} n) and O(n^{5/6} polylog n), depending on the distance measure used, for points in ℝ². These results can be extended to work in higher dimensions as well. Since the query times are still fairly large we also consider approximations. If we are allowed to report a color that appears at least (1-ε)f^* times, where f^* is the frequency of the most frequent color, we obtain a query time of O(log n + log log_{1/(1-ε)} n) in ℝ¹ and expected query times ranging between Õ(n^{1/2}ε^{-3/2}) and Õ(n^{1/2}ε^{-5/2}) in ℝ² using near-linear space (ignoring polylogarithmic factors).
Cite as

Thijs van der Horst, Maarten Löffler, and Frank Staals. Chromatic k-Nearest Neighbor Queries. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.ESA.2022.67,
  author =	{van der Horst, Thijs and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{Chromatic k-Nearest Neighbor Queries}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.67},
  URN =		{urn:nbn:de:0030-drops-170055},
  doi =		{10.4230/LIPIcs.ESA.2022.67},
  annote =	{Keywords: data structure, nearest neighbor, classification}
}
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