Source author record

Jacobus Conradi

Jacobus Conradi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Geometry

Catalog footprint

What is connected

3works

1topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2024arXiv

Revisiting the Fréchet distance between piecewise smooth curves

Since its introduction to computational geometry by Alt and Godau in 1992, the Fréchet distance has been a mainstay of algorithmic research on curve similarity computations. The focus of the research has been on comparing polygonal curves, with the notable exception of an algorithm for the decision problem for planar piecewise smooth curves due to Rote (2007). We present an algorithm for the decision problem for piecewise smooth curves that is both conceptually simpler and naturally extends to the first algorithm for the problem for piecewise smooth curves in $\mathbb{R}^d$. We assume that the algorithm is given two continuous curves, each consisting of a sequence of $m$, resp.\ $n$, smooth pieces, where each piece belongs to a sufficiently well-behaved class of curves, such as the set of algebraic curves of bounded degree. We introduce a decomposition of the free space diagram into a controlled number of pieces that can be used to solve the decision problem similarly to the polygonal case, in $O(mn)$ time, leading to a computation of the Fréchet distance that runs in $O(mn\log(mn))$ time. Furthermore, we study approximation algorithms for piecewise smooth curves that are also $c$-packed for some fixed value $c$. We adapt the existing framework for $(1+ε)$-approximations and show that an approximate decision can be computed in $O(cn/ε)$ time for any $ε> 0$.

preprint2022arXiv

Faster Approximate Covering of Subcurves under the Fréchet Distance

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(k\log(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 $\widetilde{O}(k^2 n + k n^3)$ time in expectation and uses $ \widetilde{O}(k n + n^3)$ space. For two dimensional input curves that are $c$-packed, we bound the expected running time by $\widetilde{O}(k^2 c^2 n)$ and the space by $ \widetilde{O}(kn + c^2 n)$. In $\mathbb{R}^d$ the dependency on $n$ instead is quadratic. 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.

preprint2022arXiv

On Computing the $k$-Shortcut Fréchet Distance

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(kn^{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+\varepsilon)$-approximate decider algorithm with running time in $O(k n^2 \log^2 n)$ for fixed $\varepsilon$. 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.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint