algorithm - CLRS:33.1-4:Show how to determine in O(n*n*lg n) time whether any three points in a set of n points are colinear? -
i going through clrs book of algorithms computational geometry. in exercise of 33.1-4 has asked "show how determine in o(n*n*lg n) time whether 3 points in set of n points colinear?" can done in o(n*n*n) time complexity taking 3 point @ time , doing cross product, not able understand how can in o(n*n*lg n) time. need help. let slope(p, q) , 2 points p , q , slope of line passing through p , q . now, 3 points, p , q , r , collinear iff slope(p,q) = slope(p,r) . thus, fixing p , can determine in o(n*log n) time if there 2 other points q , r such pqr line. done compute slope(p,q) other points q in set of n points, , checking if there repetitions - use set-like structure or sort , check duplicates. now, iterate on choices p , giving runtime of o(n*n*log n) .