Tuesday, January 11, 2011

Collinear points 1/11/11

There are n points in 2d space with they (x,y) co-ordinates. Find the maximum set of points that are collinear?

PS: hard one if you want to be under cubic complexity. It is what you should expect for 1/11/11 -- those are some sort of segments where collinear points can lie.

1 comment:

  1. What about this: take point p, sort others respect to the angle around p (n log n) and scan and find largest subsequence (n). So total cost is O(n^2 log n).
    Maybe it can be done even better ...

    ReplyDelete