Как найти независимые точки в единичном квадрате в O(n log n)?

Question

Рассмотрим единичный квадрат, содержащий n 2D точек. Мы говорим, что две точки p и q независимы в квадрате, если евклидово расстояние между ними больше 1. Единичный квадрат может содержать не более 3 взаимно независимых точек. Я хотел бы найти эти 3 взаимно независимые точки в данном единичном квадрате в O(n log n). Является ли это возможным? Пожалуйста, помогите мне.

Можно ли решить эту проблему в O(n^2) без использования каких-либо пространственных структур данных, таких как Quadtree, kd-tree и т. Д.?

Answer 1

Используйте пространственную структуру данных, такую ​​как Quadtree, для хранения ваших точек. Каждый узел в дереве квадрантов имеет ограничивающий прямоугольник и набор из 4 дочерних узлов, а также список точек (пустой, за исключением конечных узлов). Точки хранятся в листовых узлах.

Точечное дерево квадрантов - это адаптация двоичного дерева, используемого для представления двумерных точечных данных. Он разделяет черты всех четырех деревьев, но является истинным деревом, поскольку центр подразделения всегда находится в точке. Форма дерева зависит от порядка обработки данных. Часто очень эффективно сравнивать двумерные упорядоченные точки данных, обычно работая за O(log n) времени.

Для каждой точки сохраните набор всех точек, которые не зависят от этой точки.

Вставьте все свои точки в квадродерево, затем выполните итерацию по точкам и используйте квадродерево, чтобы найти точки, которые не зависят от каждой из них:

main()
{
     for each point p
         insert p into quadtree
         set p's set to empty

     for each point p
         findIndependentPoints(p, root node of quadtree)
}

findIndependentPoints(Point p, QuadTreeNode n)
{
     Point f = farthest corner of bounding box of n
     if distance between f and p < 1
         return  // none of the points in this node or
                 // its children are independent of p

     for each point q in n
         if distance between p and q > 1
             find intersection r of q's set and p's set
             if r is non-empty then
                 p, q, r are the 3 points -> ***SOLVED***
             add p to q's set of independent points
             add q to p's set of independent points

     for each subnode m of n (up 4 of them)
         findIndependentPoints(p, m)
}

Вы могли бы ускорить это:

find intersection r of q's set and p's set

сохраняя каждый набор как quadtree. Тогда вы могли бы найти пересечение, выполнив поиск в дереве квадрантов q для точки, независимой от p, используя ту же самую методику раннего выхода:

// find intersection r of q's set and p's set:
//     r = findMututallyIndependentPoint(p, q's quadtree root)

Point findMututallyIndependentPoint(Point p, QuadTreeNode n)
{
     Point f = farthest corner of bounding box of n
     if distance between f and p < 1
         return  // none of the points in this node or
                 // its children are independent of p

     for each point r in n
         if distance between p and r > 1
             return r

     for each subnode m of n (up 4 of them)
         findMututallyIndependentPoint(p, m)
}

Альтернативой использованию Quadtrees является использование деревьев Kd, которые создают более сбалансированные деревья, где каждый листовой узел находится на одинаковой глубине от корня. Алгоритм поиска независимых точек в этом случае будет таким же, за исключением того, что для каждого узла в структуре данных будет только до 2, а не 4 дочерних узлов, а ограничивающие рамки на каждом уровне будут иметь переменный размер.

Answer 2

Это неправильное решение. Пожалуйста, не отрицайте. Сохранено только для комментариев. Если кто-то находит другое решение, основанное на наименьшем вмещающем круге, пожалуйста, поместите ссылку в качестве комментария.

---

1. Решите проблему наименьшего круга.
2. Если диаметр круга <= 1, вернуть ноль.

3. Если круг определяется 3 точками, проверьте, которые являются "взаимно независимыми". Если их всего два, попробуйте найти третий по итерации.

4. Если окружность определяется 2 точками, они "взаимно независимы". Попробуйте найти третий по итерации.

Задача наименьшего круга может быть решена в O(N), поэтому вся сложность задачи также равна O(N).

Answer 3

Вы можете попробовать это.

Pick the top left point (Y) with coordinate (0,1). Calculate distance from each point from the List to point Y.
Sort the result in increasing order into SortedPointList (L)
If the first point (A) and the last point (B) in list L are independent:
    Foreach point P in list L:
        if P is independent to both A and B:
             Return A, B, P
Pick the top right point (X) with coordinate (1,1). Calculate distance from each point from the List to point X.
Sort the result in increasing order into SortedPointList (S)
If the first point (C) and the last point (D) in list L are independent:
    Foreach point O in list S:
        if P is independent to both C and D:
             Return C, D, O
Return null