Какой наиболее эффективный алгоритм поиска прямой линии, проходящей через большинство точек?

Question

Проблема:

N точек даны на двухмерной плоскости. Какое максимальное количество точек на одной прямой линии?

Задача имеет решение O (N ² ): пройдите каждую точку и найдите количество точек, имеющих одинаковые dx / dy относительно текущей точки. Для эффективности сохраняйте dx / dy отношений в хэш-карте.

Есть ли лучшее решение этой проблемы, чем O (N ² )?

Answer 1

Вероятно, нет решения этой проблемы, которое было бы значительно лучше, чем O (n ^ 2) в стандартной модели вычислений.

Проблема нахождения трех коллинеарных точек сводится к проблеме нахождения линииэто проходит через большинство точек, и нахождение трех коллинеарных точек является трудностью 3SUM, означая, что решение этого вопроса менее чем за O (n ^ 2) времени будет основным теоретическим результатом.

См. предыдущийвопрос о нахождении трех коллинеарных точек.

Для справки (используя известное доказательство) предположим, что мы хотим ответить на задачу 3SUM, такую ​​как поиск x, y, z в списке X, такой, что x + y+ z = 0. Если бы у нас был быстрый алгоритм для коллинеарной точечной задачи, мы могли бы использовать этот алгоритм для решения задачи 3SUM следующим образом.

Для каждого x в X создайте точку (x, x ^ 3) (пока мы предполагаем, что элементы X различны).Затем проверьте, существуют ли три коллинеарные точки среди созданных точек.

Чтобы убедиться, что это работает, обратите внимание, что если x + y + z = 0, то наклон линии от x до y равен * 1013.*

(y ^ 3 - x ^ 3) / (y - x) = y ^ 2 + yx + x ^ 2

, а наклон линии от x до z равен

(z ^ 3 - x ^ 3) / (z - x) = z ^ 2 + zx + x ^ 2 = (- (x + y)) ^ 2 - (x + y) x + x ^ 2 =x ^ 2 + 2xy + y ^ 2 - x ^ 2 - xy + x ^ 2 = y ^ 2 + yx + x ^ 2

И наоборот, если наклон от x до y равен наклону от x доz тогда

y ^ 2 + yx + x ^ 2 = z ^ 2 + zx + x ^ 2,

, что означает, что

(y - z) (x+ y + z) = 0,

, поэтому достаточно либо y = z, либо z = -x - y, чтобы доказать, что сокращение действительно.

Если в X есть дубликаты, высначала проверьте, является ли x + 2y = 0 для любого элемента x и дублирующего элемента y (в линейное время, используя хэширование или время O (n lg n), используя сортировку), а затем удалите дубликаты, прежде чем переходить к коллинеарной задаче нахождения точки.*

Answer 2

Hough Transform может дать вам приблизительное решение.Это приблизительно, потому что метод биннинга имеет ограниченное разрешение в пространстве параметров, поэтому максимальный бин даст вам ограниченный диапазон возможных линий.

Answer 3

Если вы ограничите задачу линиями, проходящими через начало координат, вы можете преобразовать точки в полярные координаты (угол, расстояние от начала координат) и отсортировать их по углу. Все точки с одинаковым углом лежат на одной линии. O (n logn)

Не думаю, что в общем случае есть более быстрое решение.

Answer 4

Как уже упоминалось, вероятно, нет способа решить общий случай этой проблемы лучше, чем O (n ^ 2).Однако, если вы предполагаете, что большое количество точек лежит на одной линии (скажем, вероятность того, что случайная точка в наборе точек лежит на линии с максимальным количеством точек, равно p) и не требует точного алгоритма,рандомизированный алгоритм более эффективен.

maxPoints = 0
Repeat for k iterations:
    1. Pick 2 random, distinct points uniformly at random
    2. maxPoints = max(maxPoints, number of points that lies on the 
       line defined by the 2 points chosen in step 1)

Обратите внимание, что на первом этапе, если вы выбрали 2 точки, лежащие на линии с максимальным количеством точек, вы получите оптимальное решение.Предполагая, что n очень велико (т. Е. Мы можем трактовать вероятность нахождения 2 желаемых точек как выборку с заменой), вероятность этого равна p ^ 2.Поэтому вероятность нахождения неоптимального решения после k итераций равна (1 - p ^ 2) ^ k.

Предположим, вы можете допустить ложно-отрицательный показатель = ошибка.Тогда этот алгоритм работает в O (nk) = O (n * log (err) / log (1 - p ^ 2)).Если n и p достаточно велики, это значительно эффективнее, чем O (n ^ 2).(т. е. предположим, что n = 1 000 000, и вы знаете, что по крайней мере 10 000 точек лежат на одной линии. Тогда n ^ 2 потребуется на величину 10 ^ 12 операций, тогда как рандомизированный алгоритм потребует на величину 10 ^ 9 операцийчтобы получить коэффициент ошибок менее 5 * 10 ^ -5.)

Answer 5

Опять решение O (n ^ 2) с псевдокодом. Идея в том, чтобы создать хеш-таблицу с самой строкой в ​​качестве ключа. Линия определяется наклоном между двумя точками, точкой, где линия пересекает ось X, и точкой, где линия пересекает ось Y.

Решение предполагает использование таких языков, как Java, C #, где для функции хеширования используются методы equals и методы хэш-кода объекта.

Создать объект (вызвать SlopeObject) с 3 полями

1. Наклон // Может быть Бесконечность
2. Точка пересечения с осью x - poix // Будет (бесконечность, некоторое значение y) или (значение x, 0)
3. Count

poix будет парами точек (x, y). Если линия пересекает ось X, poix будет (некоторое число, 0). Если линия параллельна оси x, то poix = (бесконечность, некоторое число), где значение y - это то, где линия пересекает ось y. Переопределить метод равных, где 2 объекта равны, если Slope и poix равны.

Хэш-код переопределяется функцией, которая предоставляет хэш-код на основе комбинации значений Slope и poix. Некоторый псевдокод ниже

Hashmap map;
foreach(point in the array a) {
    foeach(every other point b) {
        slope = calculateSlope(a, b);
        poix = calculateXInterception(a, b);
        SlopeObject so = new SlopeObject(slope, poix, 1); // Slope, poix and intial count 1.
        SlopeObject inMapSlopeObj = map.get(so);
        if(inMapSlopeObj == null) {
            inMapSlopeObj.put(so);
        } else {
            inMapSlopeObj.setCount(inMapSlopeObj.getCount() + 1);
        }
    }
}
SlopeObject maxCounted = getObjectWithMaxCount(map);
print("line is through " + maxCounted.poix + " with slope " + maxCounted.slope);

Answer 6

Маловероятно, что алгоритм $ o (n ^ 2) $ существует, поскольку проблема (даже проверки того, что 3 точки в R ^ 2 коллинеарны) является сложной 3 * (http://en.wikipedia.org/wiki/3SUM)

Answer 7

Это не лучшее решение, чем O (n ^ 2), но вы можете сделать следующее:

1. Для каждой конвертированной точки сначала конвертируйте ее, как если бы она была в (0,0), а затем выполните эквивалентный перевод для всех остальных точек, переместив их на то же расстояние x, y, которое необходимо для перемещения исходной выбранной точки.

2. Переведите этот новый набор переведенных точек.к углу относительно нового (0,0).

3. Сохраните максимальное количество точек (MSN), которые находятся под каждым углом.

4. Выберите максимальное сохраненное значениеномер (MSN), и это будет решением