Finding the optimal depth/ranges in a set of quad trees to optimize retrieval of points in bounding box

Question

If I have a set of quad tree (say on a Hilbert curve) what would be a good way to approach finding the optimum (or good enough) set of ranges at particular depth.

For example, if I'm searching for points between the bounding box 0,0 and 1,3 then I can apply the following naive ranges:

• Depth 1 - Range 0,0-1,0 (~33% search space)
• Depth 2 - Ranges 0,0-1,0 and 1,0-0,1 (~13% search space)
• Depth 3 - Ranges 0,0-1,0 and 1,3-0,3 (~9.8% search space)

Clearly depth 3 for this search is optimal but the reduced search space has only dropped a small amount compared to the drop from depth 1 to depth 2.

At (much) bigger depths, or with searches that cross boundaries, is there a good algorithm(s) for estimating the difference between various depths, or ideally picking a mix of ranges at different depths that ideally cover the bounding box.

I'm not interested in polygons specifically but bonus points if there is a solution that works for polygons.

Answer 1

When you use a hilbert curve it's a spatial index it's not a quadtree. A quadtree has also some limitations for example how many points you can store. So, on a hilbert curve it's better to use small tiles so the bounding box can fit nice.

Answer 2

Althoug your question needs more details, some answers:

You can estimate the depth of a quad by log4(N).
(Take the logarithm of base 4 of the number of elements N.)

Depeending on the type of quadtree you can limit the maximum depth to that number.

The order of inserting the elements influences the structure of the quad. Pre sorting the data before inserting can improve a bit the quad structure. The type of pre sort depens on the quad. if you use a hilbert backed up quad, you could pre sort the data by hilbert index.