Находя самый низкий наклон n ^ 2 линий

Учитывая P = {p ₁,..., p _n} разных точек, которые определяют n ² напишите алгоритм который находит линию, которая имеет самый низкий угол (наименьшее абсолютное значение) с O (n lgn) наихудшей сложностью.

Ответ 1

Отсортируйте точки в зависимости от их позиции y (n log n time, используя любое количество известных алгоритмов). Пройдите список по порядку, от 0 до n - 1, сравнивая склоны каждой пары точек с тем, что вы обнаружили, является самым низким наклоном. (это n времени).

В целом, это будет O (n log n).

В псевдокоде:

Let P be the list of points (this list starts at 1)
n = P.length
S = quicksort("a.y < b.y", P) // or some other O(n log n) algorithm
bestSlope = float.inf
let p1 and p2 be points
for i = 1 to n-1:
    currSlope = abs((P[i].y - P[i+1].y) / (P[i].x - P[i+1].x))
    if currSlope < bestSlope:
        bestSlope = currSlope
        p1 = P[i]
        p2 = P[i+1]

Ответ 2

Теорема:

Учитывая множество точек P.
Выберите две точки A и C в P такие, что линия AC имеет наименьший абсолютный наклон (как определено в вопросе).
Для вырожденного случая, когда несколько пар точек имеют один и тот же наклон, пусть AC - самый короткий отрезок линии с этим уклоном.
Тогда в P нет других точек с Y-координатой между A и C.

Доказательство (от противного):

Предположим, что существует хотя бы одна другая точка, B, чья координата Y находится между A и C.
Тогда существуют три возможных случая:
- B является колинейным с A и C. Тогда линии AB или BC имеют тот же наклон, что и AC, но оба они короче AC. Противоречие.
- B попадает в полуплоскость "выше" AC. Тогда линия AB имеет более низкий наклон, чем AC. Противоречие.
- B попадает в полуплоскость "ниже" AC. Тогда линия BC имеет более низкий наклон, чем AC. Противоречие.
Все случаи приводят к противоречию, поэтому между A и C не возникает точек.
QED.

С помощью этой теоремы вы можете четко использовать алгоритм @Zshazz для поиска правильной пары - потому что они будут ближайшими соседями - в O(n*log n).