کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431259 688489 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Range search on tuples of points
ترجمه فارسی عنوان
محدوده جستجو بر روی تابع امتیاز
کلمات کلیدی
الگوریتم ها، ساختارهای داده، هندسه محاسباتی، پردازش پرس و جو فضایی، محدوده جستجو، تحول هندسی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Range search is a fundamental query-retrieval problem, where the goal is to preprocess a given set of points so that the points lying inside a query object (e.g., a rectangle, or a ball, or a halfspace) can be reported efficiently. This paper considers a new version of the range search problem: Several disjoint sets of points are given along with an ordering of the sets. The goal is to preprocess the sets so that for any query point q and a distance δ, all the ordered sequences (i.e., tuples) of points can be reported (one per set and consistent with the given ordering of the sets) such that, for each tuple, the total distance traveled starting from q and visiting the points of the tuple in the specified order is no more than δ. The problem has applications in trip planning, where the objective is to visit venues of multiple types starting from a given location such that the total distance traveled satisfies a distance constraint. Efficient solutions are given for the fixed distance and variable distance versions of this problem, where δ is known beforehand or is specified as part of the query, respectively.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 30, January 2015, Pages 1–12
نویسندگان
, , , ,