Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/23453
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | KUIJPERS, Bart | - |
dc.contributor.author | Revesz, Peter Z. | - |
dc.date.accessioned | 2017-04-06T14:54:41Z | - |
dc.date.available | 2017-04-06T14:54:41Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | ISPRS International Journal of Geo-Information, 6(3) (Art N° 82) | - |
dc.identifier.issn | 2220-9964 | - |
dc.identifier.uri | http://hdl.handle.net/1942/23453 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.rights | ISPRS International Journal of Geo-Information is an open access journal. | - |
dc.subject.other | spatial data structures; point location queries; nearest point queries; selectivity estimation | - |
dc.title | A Dynamic Data Structure to Efficiently Find the Points below a Line and Estimate Their Number | - |
dc.type | Journal Contribution | - |
dc.identifier.issue | 3 | - |
dc.identifier.volume | 6 | - |
local.format.pages | 13 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | Kuijpers, B (reprint author), UHasselt Hasselt Univ, B-3590 Diepenbeek, Belgium. bart.kuijpers@uhasselt.be; revesz@cse.unl.edu | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
local.bibliographicCitation.artnr | 82 | - |
dc.identifier.doi | 10.3390/ijgi6030082 | - |
dc.identifier.isi | 000398732200025 | - |
item.fullcitation | KUIJPERS, Bart & Revesz, Peter Z. (2017) A Dynamic Data Structure to Efficiently Find the Points below a Line and Estimate Their Number. In: ISPRS International Journal of Geo-Information, 6(3) (Art N° 82). | - |
item.validation | ecoom 2018 | - |
item.contributor | KUIJPERS, Bart | - |
item.contributor | Revesz, Peter Z. | - |
item.fulltext | With Fulltext | - |
item.accessRights | Open Access | - |
crisitem.journal.eissn | 2220-9964 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ijgi-06-00082.pdf | Published version | 524.61 kB | Adobe PDF | View/Open |
Page view(s)
58
checked on Sep 7, 2022
Download(s)
108
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.