Search Results

Documents authored by van der Horst, Thijs

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact