Учитывая ряд точек, найдите, коллинеарна ли какая-либо из трех точек

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

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

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

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

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

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