Каков наилучший алгоритм поиска, если любые три точки коллинеарны в наборе точек, скажем n. Пожалуйста, также объясните сложность, если это не тривиально.
Спасибо
Bala
Каков наилучший алгоритм поиска, если любые три точки коллинеарны в наборе точек, скажем n. Пожалуйста, также объясните сложность, если это не тривиально.
Спасибо
Bala
Если вы можете найти лучший алгоритм 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), и у вас уже есть его: -)
Простой алгоритм времени и пространства O (d * N ^ 2), где d - размерность, а N - количество точек (возможно, не оптимальное):
Другое простое (возможно, даже тривиальное) решение, которое не использует хеш-таблицу, работает в O (n 2 log n) времени и использует O (n) пространство:
Пусть S
- множество точек, мы опишем алгоритм, который выясняет, содержит или нет S
три коллинеарные точки.
o
в S
выполните:
L
параллельно оси x
с помощью o
.S
ниже L
, с ее отражением. (Например, если L
- ось x
, (a,-x)
для x>0
после отражения станет (a,x)
. Пусть новый набор точек S'
p
в S'
является прямым углом отрезка po
с линией L
. Сопоставим точки S'
по их углам.S'
. Если есть две последовательные точки, коллинеарные с помощью o
- верните истину.Цикл запускает n
раз, и каждая итерация выполняет шаги nlog n
. Нетрудно доказать, что если на линии будет три точки, они будут найдены, и мы ничего не найдем.