Space partitioning algorithm

Posted by Karol Kolenda on Stack Overflow See other posts from Stack Overflow or by Karol Kolenda
Published on 2010-06-02T16:21:33Z Indexed on 2010/06/02 16:24 UTC
Read the original article Hit count: 659

Filed under:
|

I have a set of points which are contained within the rectangle. I'd like to split the rectangles into subrectangles based on point density (giving a number of subrectangles or desired density, whichever is easiest).

The partitioning doesn't have to be exact (almost any approximation better than regular grid would do), but the algorithm have to cope with the large number of points - approx. 200 millions. The desired number of subrectangles however is substantially lower (around 1000).

Does anyone knows any algorithm which may help me with this particular task?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about algorithm-design