ON A NEAREST-NEIGHBOR PROBLEM IN MINKOWSKI AND POWER METRICS
Date
2001-02-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science