de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

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

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44464

Funke,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44975

Malamatos,  Theocharis
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45000

Matijevic,  Domagoj
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45758

Wolpert,  Nicola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Funke, S., Malamatos, T., Matijevic, D., & Wolpert, N. (2006). (Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram. In 18th Canadian Conference on Computational Geometry (pp. 23-26). Kingston, Ontario, K7L 3N6, Canada: School of Computing, Queen's University.

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.