Polynomial time algorithm solves exact one two center problem for curves
Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fréchet distance
Computational GeometryData Structures and Algorithms
Summary
The paper addresses a complex problem of finding a single center curve that best represents a group of input curves, measured by continuous Fréchet distance. Prior solutions existed only for simpler discrete versions or approximations. The authors developed an exact algorithm that runs in a reasonable (polynomial) time for curves in various dimensions, improving over previous work. They also provide faster approximations and specialized algorithms for certain curve restrictions.
What this means in practice
- •For geographic information system developers: Improve curve clustering by exactly computing center paths under continuous Fréchet distance for mapping and spatial data simplification.
- •For robotics navigation engineers: Enable efficient path summarization by finding representative routes from trajectory data with guaranteed accuracy in continuous space.
Authors
Soumya Bhattacharya, Serene Rasheed, Sasanka Roy
Abstract
In this paper, we explore the $(1,2)$-center problem for polygonal curves under continuous Fréchet distance. The $(k,\ell)$-center problem, in general, is known to be NP-hard. Aronov, Filtser, Horton, Katz, and Sheikhan (WADS'19) gave a polynomial-time algorithm for the $(1,2)$-center of curves in the plane under the discrete Fréchet distance. To the best of our knowledge, the $(1,2)$-center under continuous Fréchet distance has not been studied yet. We present a polynomial time algorithm to solve the problem exactly under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm, running in $O\bigr((n^2r+nr^2)^{2+ε}\bigl)$ time for curves in the plane where $r$ is the number of input curves and $n$ is the maximum complexity of any curve. Further, for curves in any dimension $d$, the expected time to compute the center using the algorithm is $O\bigr((n^2r+nr^2)^{2(d-1)+ε}\bigl)$. We have also shown that an $(1+\widetildeε)-$factor approximation of $(1,2)$-center can be computed in $O(n^2r+nr^2+1/ε^s)$ time for any $ε>\widetildeε>0$ and some constant $s$ for curves in the plane. For curves in the plane, we have shown that, with the center restricted to be horizontal, we can compute the exact center in $O(n^2r+nr^2)$ time. An algorithm has been introduced to find a $3$-factor approximation of the $(1,2)$-center in time linear in the number of curves. A formulation was introduced by de Berg, Mehrabi, and Ophelders (CCCG'17) to measure Fréchet distance between a curve and a query segment under $\mathbb{L}_2$ norm for curves in the plane. We have shown the formulation is valid under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm for curves in $\mathbb{R}^d$.