i have an answer to ur first question. it is n^2 lgn, but its quite a long procedure and I am sure there must be somethng better.
1. set up and nXn matrix, where the entry at (i,j) is the directed slope between points i and j. this is n^2
2. sort each row of this matrix. sorting one row is nlogn, and n rows leads to n^2 lgn
3. Finally traverse each row and find out if adjacent elements are the same.
So in essence I am seeing if the slope of the line between point i and point j, is same as that between point i and point k. if so, i,j and k they are collinear.
One general request to all of u. Lets have jus one question per thread. So there will be a coherance across the entire thread if we discuss only one prob.
-Vijay
On 11/30/05, pramod <[EMAIL PROTECTED]> wrote:
1) Design a O (n^2 log(n) ) algorithm to find if any three points in a
set of n points in a plane are collinear
2) Design a O(n log(n) ) algorithm to check if two simple polygons
intersect
