Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear.
The problem is I started with general definition but I cannot continue to actually solving the problem.
What can we say about collinear points in general, 3 points $a,b,c$ are collinear if the distance $d(a,c) = d(a,b)+d(b,c)$ in the case when $b$ is between $a$ and $c$.
The naive approach has $O(n(n-1)(n-2))=O(n^3)$ time complexity.
How to solve this problem, what should be the next step?
Asked By : com
Answered By : sxu
One simple way is to fix a point $x$, compute the slope of the line $xy$ and store it in a hash table for every other point $y$. If there is a collision, then we have collinear points involving $x$. This takes $O(n)$ (if we assume hash table operations take $O(1)$). We then do this for every point $x$ in time $O(n^2)$.
Also if you are aware of the point-line duality (please refer to Artium's comment below), this reduces to checking the $n^2$ possible intersections of $n$ lines, but also makes use of hash tables.
Also it is open whether this can be done in sub-quadratic time as this problem is 3-SUM hard, please refer to this answer.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2453
0 comments:
Post a Comment
Let us know your responses and feedback