Priority Queue, why isn't the first occurrence of a leaf node the closet object to query?

[wangwalton]

In the provided pseudocode for distance queries, why doesn't it work if we return after calculating distance after if subtree is a leaf? Shouldn't any nodes within object boxes within AABBTree hold longer distances to the query point, so the first time that a subtree is leaf be the closest distance?

// initialize a queue prioritized by minimum distance
d_r ← distance to root's box
Q.insert(d_r, root)
// initialize minimum distance seen so far
d ← ∞
while Q not empty 
  // d_s: distance from query to subtree's bounding box
  (d_s, subtree) ← Q.pop
  if d_s < d
    if subtree is a leaf
      d ← min[ d , distance from query to leaf object ]
    else
      d_l ← distance to left's box
      Q.insert(d_l ,subtree.left)
      d_r ← distance to right's box
      Q.insert(d_r ,subtree.right)

[honglin-c]

There might be another subtree in the queue containing a leaf node with a shorter distance, since it's a breadth-first search.

[wangwalton]

Please explain where the following two assumptions are wrong, or if I'm missing something else:

1. If a node is in the priority queue, that means it has a longer distance than the node that is currently being processed

2. any nodes of the subtree of a node in the priority queue should have a longer distance than the node in the priority queue

Based on that two assumptions, why is it not valid to say that a queue should not contain any leaf nodes with a shorter distance, when the first leaf node is found?

[honglin-c]

Oops... Sorry, I miss the fact that it's a priority queue rather than a simple queue. Yes, you are right. I think just returning from after calculating min distance after if subtree is a leaf should be fine.

[honglin-c]

@dilevin Just make sure that I didn't say anything misleading... Do you think we can just return after calculating distance after if subtree is a leaf ? Should we modify the provided pseudocode?

[kyokeunpark]

From my personal experience, returning right after first leaf occurrence led me to incorrect outputs... Not entirely sure why

[wangwalton]

Yeah I have tried that as well and led to incorrect outputs. That's why I'm very puzzled and wonderring where my described logic is wrong

[honglin-c]

I tried that in the provided solution and it still worked correctly. Probably there is something wrong elsewhere. (But as long as your program runs correctly without the early returning, we're not going to deduct any points because of this. )

[kyewei]

The queue is based on a lower bound to a group of objects in a box, computed by the distance to the bbox, but that's not the actual distance to the objects inside the box. I assume that the correct output will probably be in the first x% of the leaf nodes processed though, and that the smallest queue distance will probably be very close to the closest-leaf distance.

Edit: can probably test it by setting a counter on "only processing lets say 100 leaf nodes" and short stopping to see if that works for a 10k query, but obviously don't do this for submission.