کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414778 | 681033 | 2013 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast Fréchet queries
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Inspired by video analysis of team sports, we study the following problem. Let P be a polygonal path in the plane with n vertices. We want to preprocess P into a data structure that can quickly count the number of inclusion-minimal subpaths of P whose Fréchet distance to a given query segment Q is at most some threshold value ε. We present a data structure that solves an approximate version of this problem: it counts all subpaths whose Fréchet distance is at most ε , but this count may also include subpaths whose Fréchet distance is up to (2+32)ε. For any parameter n≤s≤n2n≤s≤n2, our data structure can be tuned such that it uses O(spolylogn) storage and has O((n/s)polylogn) query time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 6, August 2013, Pages 747–755
Journal: Computational Geometry - Volume 46, Issue 6, August 2013, Pages 747–755
نویسندگان
Mark de Berg, Atlas F. Cook IV, Joachim Gudmundsson,