Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45486
Title: ON A NEAREST-NEIGHBOR PROBLEM IN MINKOWSKI AND POWER METRICS
Authors: Gavrilova, Marina
Keywords: Computer Science
Issue Date: 6-Feb-2001
Abstract: This report presents an efficient algorithm based on the generalized Voronoi diagram construction for solving the nearest-neighbor problem in the plane. The input for the problem is the set of circular sites S with varied radii, the query point p and the metric (Minkowski or power) according to which the site, neighboring the query point, is to be reported. The IDG/NNM software was created that allowed the experimental study of the posed problem. The performance of the method was tested on large data sets with such parameters as the number of sites, distribution of their radii, site configuration, density of packing, and the number of searches, varied. The efficiency of the generalized Voronoi diagram method was compared against the k-d tree method for finding the nearest-neighbor. The results demonstrate that the Voronoi diagram method outperforms the k-d tree method for all testes input site configurations, including the silo granular-type material model. Finally, the similarity between the nearest-neighbor relationship in the Minkowski and power metrics is worth noticing.
URI: http://hdl.handle.net/1880/45486
Appears in Collections:Gavrilova, Marina

Files in This Item:
File Description SizeFormat 
2001-680-03.ps1.34 MBPostscriptView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.