Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A O(n*log(n)) algorithm to find the segment (among n*n segments) with the lowest slope

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.

like image 726
user1387682 Avatar asked Aug 29 '12 22:08

user1387682


2 Answers

Theorem:

  • Given a set of points P.
  • Choose two points A and C in P such that the line AC has the smallest absolute slope (as defined in the question).
  • For the degenerate case where multiple pairs of points have the same slope, let AC be the shortest line segment with that slope.
  • Then there exist no other points in P with a Y-coordinate between A and C.

Proof (by contradiction):

  • Suppose there is at least one other point, B, whose Y-coordinate is between A and C.
  • Then there exist three possible cases:
    • B is co-linear with A and C. Then the lines AB or BC have the same slope as AC, but both of them are shorter than AC. Contradiction.
    • B falls in the half-plane "above" AC. Then the line AB has a shallower slope than AC. Contradiction.
    • B falls in the half-plane "below" AC. Then the line BC has a shallower slope than AC. Contradiction.
  • All cases result in contradiction, therefore no points occur between A and C.
  • QED.

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).

like image 194
EthanB Avatar answered Sep 20 '22 12:09

EthanB


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]
like image 29
Chris Cain Avatar answered Sep 20 '22 12:09

Chris Cain