Title :
An optimal algorithm to construct all Voronoi diagrams for k nearest neighbor search in T2
Author :
De Rezende, Pedro J. ; Westrupp, Rodrigo B.
Author_Institution :
Inst. de Comput., Univ. Estadual de Campinas, Sao Paulo, Brazil
Abstract :
We generalize to the oriented projective plane T2 an algorithm for constructing all order k Voronoi diagrams in the Euclidean plane. We also show that, for fixed k and for a finite set of sites, an order k Voronoi diagram in T2 has an exact number of regions. Furthermore, we show that the order k Voronoi diagram of a set of n sites in T2 is antipodal to its order n-k Voronoi diagram, ∀k: 1⩽k<n
Keywords :
computational geometry; search problems; set theory; Euclidean plane; T2; Voronoi diagrams; antipodal; finite set; fixed k; k nearest neighbor search; optimal algorithm; order k Voronoi diagram; order k Voronoi diagrams; oriented projective plane; Artificial intelligence; Euclidean distance; H infinity control; Nearest neighbor searches;
Conference_Titel :
Computer Graphics and Image Processing, 1999. Proceedings. XII Brazilian Symposium on
Conference_Location :
Campinas
Print_ISBN :
0-7695-0481-7
DOI :
10.1109/SIBGRA.1999.805592
