Range search on tuples of points

Akash Agrawal, Saladi Rahul, Yuan Li, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalJournal of Discrete Algorithms
Volume30
DOIs
StatePublished - Jan 1 2015

Bibliographical note

Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.

Keywords

  • Algorithms
  • Computational geometry
  • Data structures
  • Geometric transformation
  • Range search
  • Spatial query processing

Fingerprint

Dive into the research topics of 'Range search on tuples of points'. Together they form a unique fingerprint.

Cite this