2
Department of Mathematical Sciences, Yazd University, Yazd, Iran
Abstract
\vspace{0.2cm} In this paper, we design a data structure for the following problem. Let $\pi$ be an $x$-monotone trajectory with $n$ vertices in the plane and $\epsilon >0$. We show how to preprocess $\pi$ and $\epsilon$ into a data structure such that for any horizontal query segment $Q$ in the plane, one can quickly determine the minimal continuous fraction of $\pi$ whose Fr{'e}chet and Hausdorff distance to the horizontal query segment $Q$ is at most some threshold value $\epsilon$. We present a data structure for this query that needs $\mathcal{O}(n\log{}n)$ preprocessing time, $\mathcal{O}(n)$ space, and $\mathcal{O}(\log{} n)$ query time. & & \vspace{0.2cm}
Saeidi, Z., Farshi, M. (2019). Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories. Journal of Algorithms and Computation, 51(2), 9-17.
MLA
Zeinab Saeidi; Mohammad Farshi. "Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories". Journal of Algorithms and Computation, 51, 2, 2019, 9-17.
HARVARD
Saeidi, Z., Farshi, M. (2019). 'Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories', Journal of Algorithms and Computation, 51(2), pp. 9-17.
VANCOUVER
Saeidi, Z., Farshi, M. Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories. Journal of Algorithms and Computation, 2019; 51(2): 9-17.
)