给定欧氏距离范围划分邻居点

Question

给定两个点 P,Q 和一个 delta，我定义了等价关系 ~=，其中如果 EuclideanDistance(P,Q) <= delta，则 P ~= Q。现在，给定一组 S 的 n 个点，在示例中 S = (A, B, C, D, E, F) 且 n = 6（事实点实际上线段的端点可以忽略不计），是否有一种算法在平均情况下比 O(n^2) 复杂度更好地找到集合的分区（子集的代表元素并不重要）？

到目前为止，试图找到这个问题的理论定义并不成功：k 均值聚类、最近邻搜索和其他对我来说似乎是不同的问题。该图显示了我在应用程序中需要执行的操作。

有什么提示吗？谢谢

编辑：而实际问题（簇附近的点给出了某种不变量）在一般情况下，应该可以比 O(n^2) 更好地解决，我的问题定义中有一个严重的缺陷： =~ 不是等价关系，因为它不是一个简单的事实尊重传递性。我认为这是这个问题不容易解决并且需要先进技术的主要原因。我很快就会发布我的实际解决方案：当近点都满足定义的 =~ 时应该有效。当极点分开的点不遵守这种关系但它们与聚集点的重心有关时，可能会失败。它适用于我的输入数据空间，但可能不适用于您的输入数据空间。有谁知道这个问题的完整正式处理（以及解决方案）？

Answer 1

重述该问题的一种方法如下：给定一组 n 2D 点，对于每个点 p 找到包含在直径 < 的圆中的点集code>delta 以 p 为中心。

简单的线性搜索给出了您提到的 O(n^2) 算法。

在我看来，这是在最坏的情况下可以做的最好的事情。当集合中的所有点都包含在直径 <= delta 的圆内时，每个 n 查询都必须返回 O(n) 点，总体复杂度为 O(n^2)。

然而，人们应该能够在更合理的数据集上做得更好。
看看这个（特别是关于空间分区的部分）和KD 树。在合理的情况下，后者应该为您提供一个子O(n^2)算法。

可能有一种不同的方式来看待问题，这种方式会带来更好的复杂性；我脑子里想不出任何东西。

Answer 2

绝对是 Quadtree 的问题。

您还可以尝试对每个坐标进行排序并使用这两个列表（排序是n*log(n)，并且您可以仅检查满足dx <= delta & 的点。另外，您可以将它们放入具有两层指针的排序列表中：一层用于解析 OX，另一层用于解析 OY。

Answer 3

对于每个点，计算距原点的距离 D(n)，这是一个 O(n) 操作。

使用 O(n^2) 算法查找 D(ab) < 的匹配项delta，跳过 D(a)-D(b) >三角洲。

由于跳过的数字（希望很大），平均而言，结果必须优于 O(n^2)。

Answer 4

这是一个 C# KdTree 实现，应该解决“查找 delta 内点 P 的所有邻居”问题。它大量使用函数式编程技术（是的，我喜欢 Python）。它已经过测试，但我对_TreeFindNearest()的理解仍然存在疑问。解决问题的代码（或伪代码）“在平均情况下，在给定 ~= 关系的情况下，划分一组 n 点，其效果优于 O(n^2)”，该问题发布在另一个答案中。

/*
Stripped C# 2.0 port of ``kdtree'', a library for working with kd-trees.
Copyright (C) 2007-2009 John Tsiombikas <[email protected]>
Copyright (C) 2010 Francesco Pretto <[email protected]>

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
OF SUCH DAMAGE.
*/

using System;
using System.Collections.Generic;
using System.Text;

namespace ITR.Data.NET
{
    public class KdTree<T>
    {
        #region Fields

        private Node _Root;
        private int _Count;
        private int _Dimension;
        private CoordinateGetter<T>[] _GetCoordinate;

        #endregion // Fields

        #region Constructors

        public KdTree(params CoordinateGetter<T>[] coordinateGetters)
        {
            _Dimension = coordinateGetters.Length;
            _GetCoordinate = coordinateGetters;
        }

        #endregion // Constructors

        #region Public methods

        public void Insert(T location)
        {
            _TreeInsert(ref _Root, 0, location);
            _Count++;
        }

        public void InsertAll(IEnumerable<T> locations)
        {
            foreach (T location in locations)
                Insert(location);
        }

        public IEnumerable<T> FindNeighborsRange(T location, double range)
        {
            return _TreeFindNeighborsRange(_Root, 0, location, range);
        }

        #endregion // Public methods

        #region Tree traversal

        private void _TreeInsert(ref Node current, int currentPlane, T location)
        {
            if (current == null)
            {
                current = new Node(location);
                return;
            }

            int nextPlane = (currentPlane + 1) % _Dimension;

            if (_GetCoordinate[currentPlane](location) <
                    _GetCoordinate[currentPlane](current.Location))
                _TreeInsert(ref current._Left, nextPlane, location);
            else
                _TreeInsert(ref current._Right, nextPlane, location);
        }

        private IEnumerable<T> _TreeFindNeighborsRange(Node current, int currentPlane,
            T referenceLocation, double range)
        {
            if (current == null)
                yield break;

            double squaredDistance = 0;
            for (int it = 0; it < _Dimension; it++)
            {
                double referenceCoordinate = _GetCoordinate[it](referenceLocation);
                double currentCoordinate = _GetCoordinate[it](current.Location);
                squaredDistance +=
                    (referenceCoordinate - currentCoordinate)
                    * (referenceCoordinate - currentCoordinate);
            }

            if (squaredDistance <= range * range)
                yield return current.Location;

            double coordinateRelativeDistance =
                _GetCoordinate[currentPlane](referenceLocation)
                    - _GetCoordinate[currentPlane](current.Location);
            Direction nextDirection = coordinateRelativeDistance <= 0.0
                ? Direction.LEFT : Direction.RIGHT;
            int nextPlane = (currentPlane + 1) % _Dimension;
            IEnumerable<T> subTreeNeighbors =
                _TreeFindNeighborsRange(current[nextDirection], nextPlane,
                    referenceLocation, range);
            foreach (T location in subTreeNeighbors)
                yield return location;

            if (Math.Abs(coordinateRelativeDistance) <= range)
            {
                subTreeNeighbors =
                    _TreeFindNeighborsRange(current.GetOtherChild(nextDirection),
                        nextPlane, referenceLocation, range);
                foreach (T location in subTreeNeighbors)
                    yield return location;
            }
        }

        #endregion // Tree traversal

        #region Node class

        public class Node
        {
            #region Fields

            private T _Location;
            internal Node _Left;
            internal Node _Right;

            #endregion // Fields

            #region Constructors

            internal Node(T nodeValue)
            {
                _Location = nodeValue;
                _Left = null;
                _Right = null;
            }

            #endregion // Contructors

            #region Children Indexers

            public Node this[Direction direction]
            {
                get { return direction == Direction.LEFT ? _Left : Right; }
            }

            public Node GetOtherChild(Direction direction)
            {
                return direction == Direction.LEFT ? _Right : _Left;
            }

            #endregion // Children Indexers

            #region Properties

            public T Location
            {
                get { return _Location; }
            }

            public Node Left
            {
                get { return _Left; }
            }

            public Node Right
            {
                get { return _Right; }
            }

            #endregion // Properties
        }

        #endregion // Node class

        #region Properties

        public int Count
        {
            get { return _Count; }
            set { _Count = value; }
        }

        public Node Root
        {
            get { return _Root; }
            set { _Root = value; }
        }

        #endregion // Properties
    }

    #region Enums, delegates

    public enum Direction
    {
        LEFT = 0,
        RIGHT
    }

    public delegate double CoordinateGetter<T>(T location);

    #endregion // Enums, delegates
}

Answer 5

以下 C# 方法与 KdTree 类、Join()（枚举作为参数传递的所有集合）和 Shuffled()（返回传递集合的打乱版本）方法一起解决了我的问题。当 referenceVectors 与 vectorsToRelocate 相同的向量时，可能会出现一些有缺陷的情况（请阅读问题中的编辑），正如我在问题中所做的那样。

public static Dictionary<Vector2D, Vector2D> FindRelocationMap(
    IEnumerable<Vector2D> referenceVectors,
    IEnumerable<Vector2D> vectorsToRelocate)
{
    Dictionary<Vector2D, Vector2D> ret = new Dictionary<Vector2D, Vector2D>();

    // Preliminary filling
    IEnumerable<Vector2D> allVectors =
        Utils.Join(referenceVectors, vectorsToRelocate);
    foreach (Vector2D vector in allVectors)
        ret[vector] = vector;

    KdTree<Vector2D> kdTree = new KdTree<Vector2D>(
        delegate(Vector2D vector) { return vector.X; },
        delegate(Vector2D vector) { return vector.Y; });
    kdTree.InsertAll(Utils.Shuffled(ret.Keys));

    HashSet<Vector2D> relocatedVectors = new HashSet<Vector2D>();
    foreach (Vector2D vector in referenceVectors)
    {
        if (relocatedVectors.Contains(vector))
            continue;

        relocatedVectors.Add(vector);

        IEnumerable<Vector2D> neighbors =
            kdTree.FindNeighborsRange(vector, Tolerances.EUCLID_DIST_TOLERANCE);

        foreach (Vector2D neighbor in neighbors)
        {
            ret[neighbor] = vector;
            relocatedVectors.Add(neighbor);
        }
    }

    return ret;
}