Given P={p1,...,pn} of different points which define n2 lines, write an algorithm that finds the line which has the lowest slope (smallest absolute value) with O(n*log(n))
time complexity in the worst case.
Theorem:
Proof (by contradiction):
With this theorem, you can clearly use @Zshazz's algorithm to find the correct pair--because they will be nearest neighbors--in O(n*log n)
.
Sort the points based on their y position (n log n time using any number of well known algorithms). Go through the list in order, from 0 to n - 1, comparing each point pairs' slopes with whatever you've discovered is the lowest slope so far. (that's n time).
Overall, that would be O(n log n).
In pseudocode:
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]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With