Is there any method more effective than quad-trees for storing and searching sets of points that are not spread uniformly on the plane?

I need to be able to add, remove and search for points that are within a specified range.

I am currently testing with quad-tree but it seems the results are less than optimal when the points are not spread uniformly enough.

The points are mostly clustered in specific areas:


  • \$\begingroup\$ The big points are actually very tight clusters of points \$\endgroup\$
    – AturSams
    Apr 8 '14 at 14:42
  • \$\begingroup\$ I think what I need is for the leaves to behave like a 2-dimensionally doubly linked list so I could loop over a certain area more quickly. \$\endgroup\$
    – AturSams
    Apr 8 '14 at 14:55
  • \$\begingroup\$ What you probably want is to walk up and down the tree to determine areas that are close by. \$\endgroup\$
    – Thomas
    Apr 8 '14 at 15:12
  • \$\begingroup\$ The answer depends on what exactly do you mean with "effective". Effective for size or effective for processing time? When the latter, for which operation (adding, removing or spatial searching) do you need to optimize? \$\endgroup\$
    – Philipp
    Apr 8 '14 at 15:16
  • \$\begingroup\$ @Philipp Thanks. Effective for search speed and insertion complexity. Deletion preferably, could be handled during idle time. So it's all right if the same points temporarily exist in multiple leaves until the application (user) is idle. \$\endgroup\$
    – AturSams
    Apr 8 '14 at 16:33

You might want to give R-trees a try. They are similar to quad-trees in that they subdivide the plane recursively; however, unlike quad-trees, they do not necessarily split up each sub-plane into equally sized, non-overlapping quarters. Instead, sub-partitions are flexible in position and size.

From wikipedia:

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object; at higher levels the aggregation of an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set.

  • \$\begingroup\$ This sounds good. I will run some tests. \$\endgroup\$
    – AturSams
    Apr 8 '14 at 14:53
  • \$\begingroup\$ It appears to be the suitable solution I was looking for. Mainly because the data is sometimes spread very sparsely and sometimes clustered very densely so a quad tree was not very suitable. \$\endgroup\$
    – AturSams
    Apr 9 '14 at 11:00
  • \$\begingroup\$ Yes, that's why I thought this datastructure might be (more) suitable for your situation. Glad I could help. \$\endgroup\$
    – Thomas
    Apr 9 '14 at 11:39
  • \$\begingroup\$ Also worth mentioning are kd-trees (very similar to rtrees) \$\endgroup\$
    – AturSams
    Apr 9 '14 at 11:57

Another similar and useful data structure is the kd-tree. It divides the k dimensional space by spiting it recursively much like an R-tree. Some differences are described here:


An important difference is that some say kd-trees are hard to balance. They are probably not suitable when you need to make changes. They are useful for making lots of queries.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.