Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/23453

Title: A Dynamic Data Structure to Efficiently Find the Points below a Line and Estimate Their Number
Authors: Kuijpers, Bart
Revesz, Peter Z.
Issue Date: 2017
Citation: ISPRS International Journal of Geo-Information, 6(3) (Art N° 82)
Abstract: A basic question in computational geometry is how to find the relationship between a set of points and a line in a real plane. In this paper, we present multidimensional data structures for N points that allow answering the following queries for any given input line: (1) estimate in O(log N) time the number of points below the line; (2) return in O(log N + k) time the k ≤ N points that are below the line; and (3) return in O(log N) time the point that is closest to the line. We illustrate the utility of this computational question with GIS applications in air defense and traffic control.
Notes: Kuijpers, B (reprint author), UHasselt Hasselt Univ, B-3590 Diepenbeek, Belgium. bart.kuijpers@uhasselt.be; revesz@cse.unl.edu
URI: http://hdl.handle.net/1942/23453
DOI: 10.3390/ijgi6030082
ISI #: 000398732200025
ISSN: 2220-9964
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version524.61 kBAdobe PDF

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