@article { author = {Saeidi, Zeinab and Farshi, Mohammad}, title = {Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories}, journal = {Journal of Algorithms and Computation}, volume = {51}, number = {2}, pages = {9-17}, year = {2019}, publisher = {University of Tehran}, issn = {2476-2776}, eissn = {2476-2784}, doi = {10.22059/jac.2019.75110}, 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}}, keywords = {Distance}, url = {https://jac.ut.ac.ir/article_75110.html}, eprint = {https://jac.ut.ac.ir/article_75110_4e3b3a30f827f265419f1d3ad7b9e08d.pdf} }