TY - JOUR

T1 - Range search on tuples of points

AU - Agrawal, Akash

AU - Rahul, Saladi

AU - Li, Yuan

AU - Janardan, Ravi

N1 - Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

KW - Algorithms

KW - Computational geometry

KW - Data structures

KW - Geometric transformation

KW - Range search

KW - Spatial query processing

UR - http://www.scopus.com/inward/record.url?scp=84922359049&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84922359049&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2014.10.006

DO - 10.1016/j.jda.2014.10.006

M3 - Article

AN - SCOPUS:84922359049

VL - 30

SP - 1

EP - 12

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

ER -