Pregled bibliografske jedinice broj: 764263
Conic nearest neighbor queries and approximate Voronoi diagrams
Conic nearest neighbor queries and approximate Voronoi diagrams // Computational geometry-theory and applications, 48 (2015), 2; 76-86 doi:10.1016/j.comgeo.2014.08.002 (međunarodna recenzija, članak, znanstveni)
CROSBI ID: 764263 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Conic nearest neighbor queries and approximate Voronoi diagrams
Autori
Funke, Stefan ; Malamatos, Theocharis ; Matijević, Domagoj ; Wolpert, Nicola
Izvornik
Computational geometry-theory and applications (0925-7721) 48
(2015), 2;
76-86
Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni
Ključne riječi
Proximity problems; Nearest neighbors; Voronoi diagram
Sažetak
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.
Izvorni jezik
Engleski
Znanstvena područja
Matematika, Računarstvo
POVEZANOST RADA
Ustanove:
Sveučilište u Osijeku, Odjel za matematiku
Profili:
Domagoj Matijević
(autor)
Citiraj ovu publikaciju:
Časopis indeksira:
- Current Contents Connect (CCC)
- Web of Science Core Collection (WoSCC)
- Science Citation Index Expanded (SCI-EXP)
- SCI-EXP, SSCI i/ili A&HCI
- Scopus
Uključenost u ostale bibliografske baze podataka::
- INSPEC
