CLRS: 33.1-4: Show me how to determine in O (n * n * lg n) time whether any three points in a set of n points are collinear?
I am reading the CLRS book "Computational Geometry Algorithms". In Exercise 33.1-4, he asked us to "show how to determine in O(n*n*lg n)
time if any three points in a set of n points are collinear?" This can be done easily in the O(n*n*n)
complexity of time by taking three points at a time and doing cross product, but I can't figure out how I can do it in O(n*n*lg n)
time. Help is needed.
source to share
Let slope(P, Q)
for any two points P
and Q
be the slope of the line passing through P
and Q
. Now three points, for example P
, Q
and R
, are collinear if f slope(P,Q) = slope(P,R)
. Thus, by fixing P
, you can determine in O(n*log n)
time if there are two other points Q
and R
such that PQR
is a string. This is easy to do by calculating slope(P,Q)
for all the other points Q
in your n
point set and checking if there is any duplication - use a fitted structure, or just sort and check for duplicates. Now we iterate over all the options for P
, giving you the runtime O(n*n*log n)
.
source to share