On finding p-th nearest neighbours of scattered points in two dimensions for small p

被引：34

作者：

Goodsell, G ^{[1
]}

机构：

[1] Inst Hydrol, Wallingford OX10 8BB, Oxon, England

来源：

COMPUTER AIDED GEOMETRIC DESIGN | 2000年 / 17卷 / 04期

基金：

英国工程与自然科学研究理事会;

关键词：

Dirichlet tessellation; Voronoi diagram; Delaunay triangulation; nearest neighbours; interpolation; contouring; Geographic Information Systems;

D O I：

10.1016/S0167-8396(00)00009-1

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a large set of scattered points in the plane, we describe a new and efficient algorithm to find, for each point, the subset of p closest points, using the Dirichlet tessellation of the set of points, for small values of p. This problem has applications to interpolation and contouring, for example, in the held of Geographic Information Systems. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：387 / 392

页数：6

共 7 条

[1]

[Anonymous], ANN NUMERICAL MATH

[2]

Davis P. J, 1975, Interpolation and Approximation

[3] SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS [J].