Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fréchet distance

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((n^{2}r+n{r}^2{)}^{2+\epsilon })$ 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((n^{2}r+n{r}^2{)}^{2(d-1)+\epsilon })$. We have also shown that an $(1+\tilde{\epsilon })-$factor approximation of $(1,2)$-center can be computed in $O(n^{2}r+n{r}^2+1/{\epsilon }^s)$ time for any $\epsilon >\tilde{\epsilon }>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^{2}r+n{r}^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$.