کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874780 | 688484 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Straight-path queries in trajectory data
ترجمه فارسی عنوان
نمایش داده های مستقیم در مسیر داده ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
داده های مسیریابی، ساختارهای داده، مشکل ساده سازی مسیر،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Inspired by sports analysis, we study data structures for storing a trajectory representing the movement of a player during a game, such that the following queries can be answered: Given two positions s and t, report all sub-trajectories in which the player moved in a more or less straight line from s to t. We consider two measures of straightness, namely dilation and direction deviation, we present efficient construction algorithms for our data structures, and we analyze their performance. We also present an O(n1.5+ε) algorithm for the following simplification problem: given a trajectory P and a threshold Ï, find a simplification of P with a minimum number of vertices such that each edge in the simplification replaces a sub-trajectory whose length is at most Ï times the length of the edge. This significantly improves the fastest known algorithm for the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 36, January 2016, Pages 27-38
Journal: Journal of Discrete Algorithms - Volume 36, January 2016, Pages 27-38
نویسندگان
Mark de Berg, Ali D. Mehrabi,