7
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Here is an explanation of point-line duality. $\endgroup$ – Artium Jun 22 '12 at 18:22
  • $\begingroup$ Thank you very much for the full answer! Artium, thank you for the duality link. $\endgroup$ – com Jun 24 '12 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.