DocumentCode
3172917
Title
Nearest-Neighbor Queries with Well-Spaced Points
Author
Gray, Chris
Author_Institution
Inst. of Oper. Syst. & Comput. Networks, Tech. Univ. Braunschweig, Braunschweig, Germany
fYear
2010
fDate
28-30 June 2010
Firstpage
42
Lastpage
49
Abstract
We assume we are given a set of points that have the property that their Voronoi diagram-restricted to some suitable bounding box-consists of only fat cells. We call such points well-spaced points. We give a linear-sized data structure for finding the nearest neighbor to a query point among well-spaced points in O(log n) time. We further show how to extend the results to higher dimensions. Finally, we show how to find the Voronoi diagram of these points in O(n log n) time in 3 dimensions.
Keywords
computational geometry; data structures; Voronoi diagram; fat cell; linear-sized data structure; nearest-neighbor queries; well-spaced points; Algorithm design and analysis; Clouds; Computer networks; Data structures; Euclidean distance; Nearest neighbor searches; Operating systems; nearest neighbor; realistic input; well-spaced points;
fLanguage
English
Publisher
ieee
Conference_Titel
Voronoi Diagrams in Science and Engineering (ISVD), 2010 International Symposium on
Conference_Location
Quebec, QC
Print_ISBN
978-1-4244-7606-0
Electronic_ISBN
978-1-4244-7605-3
Type
conf
DOI
10.1109/ISVD.2010.27
Filename
5521408
Link To Document