Geometric search on point-tuples
2016-06
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Geometric search on point-tuples
Authors
Published Date
2016-06
Publisher
Type
Thesis or Dissertation
Abstract
Computational geometry is a branch of computer science that deals with the algorithmic aspects of geometric problems. Nearest neighbor search and range search are two fundamental geometric search problems in computational geometry. Despite the long history of these problems, the majority of the research until now has been focused on simple objects such as points. However, many applications such as trip planning under budget constraint, routing, task allocation, wireless sensor networks, etc. require querying more complex objects, such as point-tuples, that are created at the query time. Motivated by such considerations, this dissertation is devoted to the design of efficient algorithms and data structures for a relatively new class of geometric search problems where the goal is to report point-tuples that satisfy certain query constraints. Given several disjoint sets of points with an ordering of the sets, two fundamental search problems are addressed. The first problem is a point-tuple version of the nearest neighbor search problem, where the goal is to report the ordered sequence (i.e., tuple) of points (one per set and consistent with the given ordering of the sets) such that the total distance traveled starting from a query point q and visiting the points of the tuple in the specified order is minimum. The second problem is a point-tuple version of the range search problem, where, for a distance constraint δ, the goal is to report all the tuples of points (again, 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 is no more than δ. In many applications, the points also have feature attributes in addition to spatial attributes (coordinates). For such datasets, three extensions of the point-tuple version of the range search problem are also studied. These extensions differ in the type of constraint applied on the output tuples, as dictated by the underlying application. The first extension applies range constraints on the feature attribute values. The second extension applies a threshold constraint on the scores of the tuples, computed from the feature attribute values using an aggregation function (e.g., sum, product, etc.). Finally, the third extension seeks the so-called skyline of the output tuples based on the feature attribute values.
Description
University of Minnesota Ph.D. dissertation. 2016. Major: Computer Science. Advisor: Ravi Janardan. 1 computer file (PDF); 120 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Agrawal, Akash. (2016). Geometric search on point-tuples. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/182157.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.