Найдите две самые дальние точки в наборе точек за линейное время (алгоритм 2-приближения)

Это может сработать, но тщательно протестируйте его на данных и проверьте:

• Удалите все дубликаты.
• Переместите все свои точки в плоскость +x, +y, +z, ....
• Найдите расстояние каждой точки от начала координат.
• Найдите минимальное и максимальное расстояние.
• Найдите индексы двух точек на минимальном и максимальном расстояниях.

Код

class FindPair(object):
    def __init__(self, points):
        self.P = points
        self.dists = [0 for i in range(len(self.P))]

    def _shifted(self):
        Pm = []
        for x, y, z in self.P:
            Pm += [(x + 10, y + 10, z + 10)]
        return Pm

    def _eucl(self, x, y, z):
        return x ** 2 + y ** 2 + z ** 2

    def _search(self):
        Pm = self._shifted()
        for i, (x, y, z) in enumerate(Pm):
            self.dists[i] = self._eucl(x, y, z)
        return self.dists

    def get_max_dist(self):
        self._search()
        min_dist, max_dist = min(self.dists), max(self.dists)
        imin, imax = self.dists.index(min_dist), self.dists.index(max_dist)
        return imin, imax

    def get_points(self):
        i, j = self.get_max_dist()
        return self.P[i], self.P[j]


base_points = ((0, 0, 0), (1, 0, 0), (1, 1, 0), (0, 1, 0), (-1, 1, 0), (-1, 0, 0), (-1, -1, 0), (0, -1, 0), (1, -1, 0),
               (0, 0, 1), (1, 0, 1), (1, 1, 1), (0, 1, 1), (-1, 1, 1), (-1, 0, 1), (-1, -1, 1), (0, -1, 1), (1, -1, 1),
               (0, 0, -1), (1, 0, -1), (1, 1, -1), (0, 1, -1), (-1, 1, -1), (-1, 0, -1), (-1, -1, -1), (0, -1, -1), (1, -1, -1))

populations = []
for i in range(100, 105):
    for j in range(200, 205):
        for k in range(300, 305):
            for x, _, _ in base_points:
                for _, y, _ in base_points:
                    for _, _, z in base_points:
                        populations += [(x + i, y + j, z + k)]

finder = FindPair(populations)
print(finder.get_points())
print(len(populations))

Принты

((99, 199, 299), (105, 205, 305))
2460375

Примечание

• Для смещения мы можем добавить большое число к x, y, z,... всех точек.

Сложность

• Временная сложность равна O(N).
• В приведенном выше примере пространство равно O(N), но вы можете сделать это константой.

Пример воздушных змеев в небе

Этот подход аналогичен набору «воздушных змеев в небе», все они привязаны к одному основанию в земле. Мы хотим найти два кайта с максимальным и минимальным расстоянием до основания в земле.

Сравнение с брутфорсом O(N ^ 2)

• Добавлено на основе комментариев.

Код

import math

class FindPair(object):
    def __init__(self, points):
        self.P = points
        self.dists = [0 for i in range(len(self.P))]

    def _shifted(self):
        Pm = []
        for x, y, z in self.P:
            Pm += [(x + 1000, y + 1000, z + 1000)]
        return Pm

    def _eucl(self, x, y, z):
        return x ** 2 + y ** 2 + z ** 2

    def _search(self):
        Pm = self._shifted()
        for i, (x, y, z) in enumerate(Pm):
            self.dists[i] = self._eucl(x, y, z)
        return self.dists

    def get_max_dist(self):
        self._search()
        min_dist, max_dist = min(self.dists), max(self.dists)
        imin, imax = self.dists.index(min_dist), self.dists.index(max_dist)
        return imin, imax

    def get_points(self):
        i, j = self.get_max_dist()
        return self.P[i], self.P[j]


class BruteForce(object):
    def __init__(self, points):
        self.P = points

    def _euclidean_distance(self, p1, p2):
        return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 + (p1[2] - p2[2]) ** 2)

    def get_max_dist(self):
        max_dist = 0
        max_pair = (None, None)
        for i in range(len(self.P)):
            for j in range(i + 1, len(self.P)):
                dist = self._euclidean_distance(self.P[i], self.P[j])
                if dist > max_dist:
                    max_dist = dist
                    max_pair = (self.P[i], self.P[j])
        return max_pair


base_points = ((0, -3, 0), (1, 3, 0), (0, 3, 0), (-1, 3, 0), (0, 1, 0))

# populations = []
# for i in range(100, 105):
#     for j in range(200, 205):
#         for k in range(300, 305):
#             for x, _, _ in base_points:
#                 for _, y, _ in base_points:
#                     for _, _, z in base_points:
#                         populations += [(x + i, y + j, z + k)]

finder = FindPair(base_points)
print(finder.get_points())
brute_force = BruteForce(base_points)
print(brute_force.get_max_dist())
# print(len(populations))

Принты

((0, -3, 0), (1, 3, 0))

((0, -3, 0), (1, 3, 0))

Комментарии

• @btilly в комментариях, похоже, прав. Хотя я еще не уверен, потому что этот подход «слишком прост» для поставленной задачи, требующей методов аппроксимации (возможно, даже NP-полных).

• Проблемы могут возникнуть, когда точки находятся слишком далеко друг от друга и имеют бесконечные размеры, и их смещение может быть непростым или вообще нежелательным или может слишком усложнить вычисления. Если у нас бесконечные измерения, то это NP-полная задача.

Однако для 1000 измерений мы можем изменить уравнение расстояния до x1 ^ 2 + x2 ^ 2 + x3 ^ 2 + ... + x1000 ^ 2.

• Если наши числа x, y, z,... слишком велики, мы могли бы нормализовать все числа до диапазона небольших чисел и использовать вычисления двойной точности.

• Есть еще кое-что, что следует принять во внимание.

Увидев некоторые идеи @user24714692, я увидел простой ответ.

1. Найдите центр c множества точек. Оно обладает тем свойством, что для любой точки p1 в точках, не находящейся в центре, должна быть другая точка p2 «по другую сторону от центра», то есть с (p1-c) ⋅ (p2-c) < 0.
2. Найдите p1, самую дальнюю точку от c. Самое дальнее расстояние между двумя точками не может быть более чем в 2 раза больше расстояния этой точки от центра.
3. Найдите p2, самую дальнюю точку от p1. Любая точка «по другую сторону центра» от p2 должна быть дальше центра. И вот (p1, p2) наш ответ.

Вот код для этого.

# This is O(d) where d is the number of dimensions.
def norm2 (point):
    return sum((point[i] * point[i] for i in range(len(point))))

# This is O(n*d)   
def center (points):
    return tuple((
        sum(point[i] for point in points)/len(points)
            for i in range(len(points[0]))
            ))

# This is O(d)
def difference (point1, point2):
    return tuple((
        point1[i] - point2[i]
            for i in range(len(point1))
            ))

# This is O(n*d)    
def farthest_from_position(points, position):
    farthest_point = points[0]
    farthest_d2 = norm2(difference(farthest_point, position))
    for point in points:
        d2 = norm2(difference(point, position))
        if farthest_d2 < d2:
            farthest_d2 = d2
            farthest_point = point
    return farthest_point

# This is O(n*d)
# Returns a pair guaranteed to be at least half the maximum distance apart.
def far_pair(points):
    c = center(points)
    p1 = farthest_from_position(points, c)
    p2 = farthest_from_position(points, p1)
    return (p1, p2)

Удивительно, но ответ на этот вопрос довольно прост:

Случайным образом выберите точку из A, найдите самую дальнюю точку B от A, верните расстояние и готово!