سامانه پشتیبانی خدمات اطلاعات

  اخبار و اعلانات

 آمار

تعداد نشریات158
تعداد شماره‌ها6,225
تعداد مقالات67,685
تعداد مشاهده مقاله114,990,675
تعداد دریافت فایل اصل مقاله89,660,127
Saeidi, Zeinab, Farshi, Mohammad. (1398). Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories. , 51(2), 9-17. doi: 10.22059/jac.2019.75110
Zeinab Saeidi; Mohammad Farshi. "Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories". , 51, 2, 1398, 9-17. doi: 10.22059/jac.2019.75110
Saeidi, Zeinab, Farshi, Mohammad. (1398). 'Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories', , 51(2), pp. 9-17. doi: 10.22059/jac.2019.75110
Saeidi, Zeinab, Farshi, Mohammad. Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories. , 1398; 51(2): 9-17. doi: 10.22059/jac.2019.75110

Fr{\'e}chet and Hausdorff Queries on $x$-Monotone Trajectories

Journal of Algorithms and Computation
مقاله 2، دوره 51، شماره 2، اسفند 2019، صفحه 9-17    اصل مقاله (261.92 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2019.75110
نویسندگان
Zeinab Saeidi1؛ Mohammad Farshi2
1Yazd University, Iran
2Department of Mathematical Sciences, Yazd University, Yazd, Iran
چکیده
\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}
کلیدواژه‌ها
distance
آمار
تعداد مشاهده مقاله: 283
تعداد دریافت فایل اصل مقاله: 240


سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب