Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|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|
|Type: ||Research Report|
|Appears in Collections: ||Research publications|
Files in This Item:
|N/A||354.91 kB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.