Conic nearest neighbor queries and approximate Voronoi diagrams (CROSBI ID 218855)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Funke, Stefan ; Malamatos, Theocharis ; Matijević, Domagoj ; Wolpert, Nicola
engleski
Conic nearest neighbor queries and approximate Voronoi diagrams
Given a cone C and a set S of n points in R^d, we want to preprocess S into a data structure so that we can find fast an approximate nearest neighbor to a query point q with respect to the points of S contained in the translation of C with apex at q. We develop an approximate conic Voronoi diagram of O(n/eps^d) size that supports conic nearest neighbor queries in O(log(n/ε)) time. Our preprocessing uses only the well-separated pair decomposition and a compressed quadtree. Previous results were restricted to simplicial cones and achieved polylogarithmic or higher query times. By increasing space to O(n/eps^(2d)) our data structure further supports queries for any cone direction and angle.
Proximity problems; Nearest neighbors; Voronoi diagram
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
48 (2)
2015.
76-86
objavljeno
0925-7721
10.1016/j.comgeo.2014.08.002