Discrete Generalized Voronoi Diagrams : Applications to Data Classification

@inproceedings{SoucheRM2004,
 abstract = { A method for computing, in any dimension, discrete Voronoi diagrams of various objects is presented. It is shown that such Voronoi diagrams can be used for multivariate data clustering and classification. The process for creating a Voronoi diagram is derived from Saito and Toriwaki’s Euclidean Distance Transform algorithm. First the Voronoi sites, that can be points, line segments, polygons, polyhedra, curves or curved surfaces are rasterized in a digital image. We then construct a distance map that represent, for each pixel of the image, the distance to the closest rasterized object. Simultaneously, a discrete version of the Voronoi diagram is computed, each Voronoi region gathering all pixels that are closer to a given object than to others. It is then shown that this image can be used for fast nearest neighbor searching. Finally, an improved version of this algorithm that can be used for creating an efficient k th nearest neighbors supervised classifier is presented. },
 author = { Souche, Laurent AND Ledez, David },
 booktitle = { 24th gOcad Meeting },
 month = { "june" },
 publisher = { ASGA },
 title = { Discrete Generalized Voronoi Diagrams : Applications to Data Classification },
 year = { 2004 }
}