FAST NEIGHBORHOOD SEARCH IN PLANAR POINT SETS

被引：13

作者：

CHETVERIKOV, D

机构：

[1] Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, H-1502

来源：

PATTERN RECOGNITION LETTERS | 1991年 / 12卷 / 07期

基金：

匈牙利科学研究基金会;

关键词：

SPATIAL NEIGHBORHOOD SEARCH; PLANAR POINT SETS;

D O I：

10.1016/0167-8655(91)90298-Z

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

A simple and practical method is proposed that facilitates fast spatial neighborhood operations in a non-ordered point list containing coordinates of a planar point set. Given a rectangular neighborhood, O(Nq) operations are needed to scan the neighborhoods of N points in the list, where q is the average number of points in the neighborhood. The method uses a data structure that requires O(N) bytes of storage. The complexity of the algorithm that structures the data is O(N).

引用

页码：409 / 412

页数：4