Проблема:
N точек заданы на двумерной плоскости. Каково максимальное количество точек на одной прямой?
Задача имеет решение O (N 2): пройдите через каждую точку и найдите число точек, которые имеют одинаковую dx / dy по отношению к текущей точке. Храните dx / dy отношения в хэш-карте для эффективности.
Есть ли лучшее решение этой проблемы, чем O (N 2)?
Вероятно, нет решения этой проблемы, которая значительно лучше, чем O (n ^ 2) в стандартной модели вычислений.
Задача о поиске трех коллинеарных точек сводится к задаче нахождения линии, проходящей через большинство точек, и нахождение трех коллинеарных точек 3SUM-hard, что означает, что решение ее менее чем за время 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 равен
(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) время с использованием сортировки), а затем удалять дубликаты до сводя к проблеме коллинеарной точки.
Если вы ограничиваете проблему линиями, проходящими через начало координат, вы можете преобразовать точки в полярные координаты (угол, расстояние от источника) и отсортировать их по углу. Все точки с одинаковым углом лежат на одной и той же линии. O (n logn)
Я не думаю, что в общем случае есть более быстрое решение.
Hough Transform может дать вам приблизительное решение. Он приближен, потому что метод биннинга имеет ограниченное разрешение в пространстве параметров, поэтому максимальный бит даст вам ограниченный диапазон возможных линий.
Маловероятно существование алгоритма $o (n ^ 2) $, так как проблема (даже проверки, если 3 точки в R ^ 2 коллинеарны) 3Sum-hard (http://en.wikipedia.org/wiki/3SUM)
Опять же решение O (n ^ 2) с псевдокодом. Идея создает хеш-таблицу с самой линией в качестве ключа. Линия определяется наклоном между двумя точками, точкой, где линия обрезает ось х и точку, где линия обрезает ось Y.
Решение предполагает, что такие языки, как Java, С#, где equals метод и методы hashcode объекта используются для хэширования.
Создайте объект (вызовите SlopeObject) с тремя полями
poix//Будет (бесконечность, некоторое значение y) или (значение x, 0) poix будет точкой (x, y). Если линия пересекает ось х, то poix будет (некоторое число, 0). Если линия параллельна оси x, то poix = (бесконечность, некоторое число), где y - значение, где линия пересекает ось y.
Переопределить метод equals, где 2 объекта равны, если Slope и poix равны.
Hashcode переопределяется функцией, которая предоставляет хэш-код на основе комбинации значений 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);
Как уже упоминалось, вероятно, нет возможности решить общий случай этой проблемы лучше, чем 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.
Предположим, вы можете терпеть ложную отрицательную скорость передачи = err. Тогда этот алгоритм работает в 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.)
Это не решение лучше, чем O (n ^ 2), но вы можете сделать следующее:
2. Переместите этот новый набор переведенных точек на угол относительно нового (0,0).
3. Сохраните максимальное количество (MSN) точек, находящихся под каждым углом.
4. Выберите максимально сохраненное число (MSN), и это будет решение