Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/21220
Title: | A Data Structure to Efficiently Answer Point Location Queries with Respect to a Line | Authors: | KUIJPERS, Bart Revesz, Peter Z. |
Issue Date: | 2015 | Abstract: | A basic question in computational geometry is to find the relationship between a set of points and a line in the real plane. In this paper, we present multidimensional data structures for N points that allow answering in O(log N + k) time the following queries: (1) Given an input line, estimate the number of points below the line, (2) Given an input line, return the k ≤ N points that are below the line, and (3) Given an input line, return the point that is closest to the line. | Notes: | Preprint submitted to Elsevier Science | Keywords: | point location queries; nearest point queries; selectivity estimation | Document URI: | http://hdl.handle.net/1942/21220 | Category: | R2 | Type: | Research Report |
Appears in Collections: | Research publications |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.