По заданному набору точек определите, являются ли какие-либо из трех точек коллинеарными.

Question

Какой наилучший алгоритм найти, если любые три точки коллинеарны в наборе точек, скажем, n. Пожалуйста, объясните сложность, если она не тривиальна.

Спасибо
Bala

Answer 1

Если вы можете придумать алгоритм лучше, чем O (N ^ 2), вы можете опубликовать его!

Это проблема 3-SUM Hard , и существует ли субквадратичный алгоритм (т. Е. Лучше, чем O (N ^ 2)), поскольку это открытая проблема. Было показано, что многие общие проблемы вычислительной геометрии (включая вашу) сложны в 3SUM, и этот класс проблем растет. Как и NP-Hardness, концепция 3SUM-Hardness оказалась полезной в доказательстве «стойкости» некоторых проблем.

Чтобы доказать, что ваша проблема сложная 3SUM, см. Превосходную статью по теме: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf

Ваша проблема появляется на стр. 3 (обычно называется 3-POINTS-ON-LINE) в вышеупомянутой статье.

Итак, наиболее известным на данный момент алгоритмом является O (N ^ 2), и он у вас уже есть: -)

Answer 2

Простой O (d * N ^ 2) алгоритм времени и пространства, где d - размерность, а N - количество точек (возможно, не оптимальное):

• Создайте ограничивающий прямоугольник вокруг набора точек (сделайте его достаточно большим, чтобы на границе не было точек)
• Для каждой пары точек вычислите линию, проходящую через них.
• Для каждой линии вычислите две ее точки столкновения с помощью ограничительной рамки.
• Две точки столкновения определяют исходную линию, поэтому, если есть какие-либо совпадающие линии, они также будут производить те же две точки столкновения.
• Используйте хэш-набор, чтобы определить, есть ли какие-либо повторяющиеся пары точек столкновения.
• Есть 3 коллинеарных точки, если и только если были дубликаты.

Answer 3

Другое простое (возможно, даже тривиальное) решение, которое не использует хеш-таблицу, выполняется за O (n ² log n) времени и использует пространство O (n):

Пусть S будет набором точек, мы опишем алгоритм, который выясняет, содержит ли S три коллинеарных точки.

1. Для каждой точки o in S выполните:
   1. Пройдите линию L параллельно оси x через o.
   2. Заменить каждую точку в S ниже L ее отражением. (Например, если L - ось x, (a,-x) для x>0 станет (a,x) после отражения). Пусть новый набор точек будет S'
   3. Угол каждой точки p в S', это прямой угол отрезка po с линией L. Давайте разберем точки S' по их углам.
   4. Пройдите через отсортированные точки в S'. Если есть две последовательные точки, которые коллинеарны с o - вернуть true.
2. Если в цикле не было найдено коллинеарных точек - вернуть false.

Цикл выполняется n раз, и каждая итерация выполняет nlog n шагов. Нетрудно доказать, что если на линии есть три точки, они будут найдены, а иначе мы ничего не найдем.