2 Search Results for "Conradi, Jacobus"

Document
DOI: 10.4230/LIPIcs.ESA.2022.28
Faster Approximate Covering of Subcurves Under the Fréchet Distance

Authors: Frederik Brüning, Jacobus Conradi, and Anne Driemel

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

Abstract
Subtrajectory clustering is an important variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number k of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given Δ to a representative curve. We focus on the case where the representative curves are line segments and approach this NP-hard problem with classical techniques from the area of geometric set cover: we use a variant of the multiplicative weights update method which was first suggested by Brönniman and Goodrich for set cover instances with small VC-dimension. We obtain a bicriteria-approximation algorithm that computes a set of O(klog(k)) line segments that cover a given polygonal curve of n vertices under Fréchet distance at most O(Δ). We show that the algorithm runs in Õ(k² n + k n³) time in expectation and uses Õ(k n + n³) space. For input curves that are c-packed and lie in the plane, we bound the expected running time by Õ(k² c² n) and the space by Õ(kn + c² n). In addition, we present a variant of the algorithm that uses implicit weight updates on the candidate set and thereby achieves near-linear running time in n without any assumptions on the input curve, while keeping the same approximation bounds. This comes at the expense of a small (polylogarithmic) dependency on the relative arclength.
Cite as

Frederik Brüning, Jacobus Conradi, and Anne Driemel. Faster Approximate Covering of Subcurves Under the Fréchet Distance. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bruning_et_al:LIPIcs.ESA.2022.28,
  author =	{Br\"{u}ning, Frederik and Conradi, Jacobus and Driemel, Anne},
  title =	{{Faster Approximate Covering of Subcurves Under the Fr\'{e}chet Distance}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{28:1--28:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.28},
  URN =		{urn:nbn:de:0030-drops-169660},
  doi =		{10.4230/LIPIcs.ESA.2022.28},
  annote =	{Keywords: Clustering, Set cover, Fr\'{e}chet distance, Approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.46
On Computing the k-Shortcut Fréchet Distance

Authors: Jacobus Conradi and Anne Driemel

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijections of the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterized version of this problem, where the number of shortcuts is bounded by a parameter k. The corresponding decision problem can be stated as follows: Given two polygonal curves T and B of at most n vertices, a parameter k and a distance threshold δ, is it possible to introduce k shortcuts along B such that the Fréchet distance of the resulting curve and the curve T is at most δ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (i) assuming the exponential-time-hypothesis (ETH), there exists no algorithm with running time bounded by n^o(k); (ii) there exists a decision algorithm with running time in O(k n^{2k+2} log n). In contrast, we also show that efficient approximate decider algorithms are possible, even when k is large. We present a (3+ε)-approximate decider algorithm with running time in O(k n² log² n) for fixed ε. In addition, we can show that, if k is a constant and the two curves are c-packed for some constant c, then the approximate decider algorithm runs in near-linear time.
Cite as

Jacobus Conradi and Anne Driemel. On Computing the k-Shortcut Fréchet Distance. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.ICALP.2022.46,
  author =	{Conradi, Jacobus and Driemel, Anne},
  title =	{{On Computing the k-Shortcut Fr\'{e}chet Distance}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.46},
  URN =		{urn:nbn:de:0030-drops-163875},
  doi =		{10.4230/LIPIcs.ICALP.2022.46},
  annote =	{Keywords: Fr\'{e}chet distance, Partial similarity, Conditional lower bounds, Approximation algorithms}
}
  • Refine by Author
  • 2 Conradi, Jacobus
  • 2 Driemel, Anne
  • 1 Brüning, Frederik

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 Approximation algorithms
  • 2 Fréchet distance
  • 1 Clustering
  • 1 Conditional lower bounds
  • 1 Partial similarity
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2022

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact