Naslov
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram

Autori
Funke, Stefan ; Malamatos, Theocharis ; Matijević, Domagoj ; Wolpert, Nicola

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceeding of 18th Canadian Conference on Computational Geometry / Rappaport, David - Kingston : School of Computing, Queen's University, 2006, 23-26

Skup
18th Canadian Conference on Computational Geometry (CCCG)

Mjesto i datum
Kingston, Kanada, 14.08.2006. - 16.08.2006

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
nearest neighbor

Sažetak
For a given point set in Euclidean space we consider the problem of finding (approximate) nearest neighbors of a query point but restricting only to points that lie within a fixed cone with apex at the query point. Apart from being a rather natural question to ask, solutions to this problem have applications in surface reconstruction and dimension detection. We investigate the structure of the Voronoi diagram induced by this notion of proximity and present approximate and exact data structures for answering cone-restricted nearest neighbor queries. In particular we develop an approximate Voronoi diagram of size $O((n/\epsilon^d)\log (1/\epsilon))$ that can be used to answer cone-restricted nearest neighbor queries in $O(\log (n/\epsilon))$ time.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA