Document Server@UHasselt >
Research >
Research publications >

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
URI: http://hdl.handle.net/1942/21220
Category: R2
Type: Research Report
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A354.91 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.