APPROXIMATE CLOSEST-POINT QUERIES IN HIGH DIMENSIONS
APPROXIMATE CLOSEST-POINT QUERIES IN HIGH DIMENSIONS
复制标题
DOI：
10.1016/0020-0190(93)90222-u
复制
发表时间：
1993-02-26
影响因子：
0.5
通讯作者：
BERN, M
中科院分区：
文献类型：
--
作者：
BERN, M
给定d维中的n个点，我们将展示如何构建空间O（d2(d)n）的数据结构，该结构在时间O（d2d log n）内近似地回答最近点查询。返回点与查询点的距离最多为真正最近点的0 （d1/2）倍。我们还展示了如何构建一个空间为O（dn log m）的数据结构，该数据结构可以在每个查询时间为O（d log n log m）的情况下以近似比率O（d3/2）回答m个最近点查询的序列。我们的数据结构是基于四叉树的。
Given n points in d dimensions, we show how to construct a data structure of space O(d2(d)n) that approximately answers closest-point queries in time O(d2d log n). The returned point is at most O(d1/2) times further from the query point than the true closest point. We also show how to construct a data structure of space O(dn log m), that-with high probability-can answer a sequence of m closest-point queries in time O(d log n log m) per query, with approximation ratio O(d3/2). Our data structures are based on quadtrees.