ON A NEAREST-NEIGHBOR PROBLEM IN MINKOWSKI AND POWER METRICS

Simple item page
dc.contributor.authorGavrilova, Marinaeng
dc.date.accessioned2008-02-26T20:32:53Z
dc.date.available2008-02-26T20:32:53Z
dc.date.computerscience2001-02-06eng
dc.date.issued2001-02-06eng
dc.description.abstractThis 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.eng
dc.description.notesWe are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.caeng
dc.identifier.department2001-680-03eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30619
dc.identifier.urihttp://hdl.handle.net/1880/45486
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleON A NEAREST-NEIGHBOR PROBLEM IN MINKOWSKI AND POWER METRICSeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
2001-680-03.ps
Size:
1.31 MB
Format:
Postscript Files
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description:
Download
Collections
Science Research & Publications