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$

1 Answer 1

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$
4
  • $\begingroup$ Here is an explanation of point-line duality. $\endgroup$
    – Artium
    Jun 22, 2012 at 18:22
  • $\begingroup$ Thank you very much for the full answer! Artium, thank you for the duality link. $\endgroup$
    – com
    Jun 24, 2012 at 3:50
  • $\begingroup$ @Artium, here is a working link to the point-line duality. $\endgroup$ Feb 29, 2020 at 18:24
  • $\begingroup$ If to assume that all point coordinates are integer (or rational) numbers AND the machine can do calculations with these numbers with limitless precision, then this answer is correct - otherwise the hash table might give you a wrong answer $\endgroup$
    – HEKTO
    May 14, 2023 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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