CODEWITHSUNDEEP
algorithmcomputational-geometry
kafee651
kafee651

Reputation: 67

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 am going through CLRS book of Algorithms for Computational Geometry. In exercise of 33.1-4 it has asked us to "Show how to determine in O(n*n*lg n) time whether any three points in a set of n points are colinear?" This can be easily done in O(n*n*n) time complexity by taking three point at a time and doing cross product, but I am not able to understand how I can do it in O(n*n*lg n) time. Need help.

Upvotes: 4

Views: 1695

Answers (1)

Pradhan
Pradhan

Reputation: 16777

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, say P, Q and R, are collinear iff slope(P,Q) = slope(P,R). Thus, 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 line. This is easily done by compute slope(P,Q) for all other points Q in your set of n points, and checking if there are any repetitions - use a set-like structure or just sort and check for duplicates. Now, iterate over all choices for P, giving you a runtime of O(n*n*log n).

Upvotes: 4

Related Questions