## -

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

blackhole
Posts: 4
Joined: Thu Jan 20, 2011 9:32 am UTC

### -

-
Last edited by blackhole on Thu Nov 27, 2014 2:19 am UTC, edited 1 time in total.

Sagekilla
Posts: 382
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

### Re: 2D Culling with Regional KD-trees

blackhole wrote:Its very hard to get into the CSE major at the college I'm in

Just out of curiosity, which uni are you at and what year are you in currently?

Hence, I'd appreciate some pointers and feedback on this first draft (which is not formatted). Thanks

0x70bb481f
0x3167c31a

But in all seriousness, I'm taking a read through right now and I'll let you know what I think.

Edit: One quick thing. I've never worked with KD-trees, but I have played around with quadtrees on occasion.

Why do you say "the quadtree is inherently fixed." I've used them to accelerate a collision detection algorithm
and a n-body simulation before, so I don't really see what you mean by "fixed" here. Do you mean like, you have
to rebuild it from the ground up if you change (for example) the position of all the objects inside it?
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.

blackhole
Posts: 4
Joined: Thu Jan 20, 2011 9:32 am UTC

### Re: 2D Culling with Regional KD-trees

I'm attending the University of Washington, whose CS program only graduates about 84 students each year and accepts about 20% of its applicants, despite the incredible demand for software developers right now.

I've rewritten that sentence to clarify the meaning as the region being static, not the tree itself. That is, the tree can't shrink or expand, only subdivide.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: 2D Culling with Regional KD-trees

You have some grammar problems.

A minor problem: "Unlike a quadtree‟s regions, these usually aren‟t square, and are not bound." should read "bounded."

A less minor problem: "we must prove that its algorithmic complexity is nearly identical, and that it is reasonably close to the quadtree in actual constant running time."

Bad formatting of "Fig. 1: A standard kd-tree, with filled implied regions" (on wrong page, not next to image), plus what you mean seems a bit stilted.

Your Fig2 needs a ... somewhere I think. The axis of each cut alternate, so as drawn the orientation of the root (P_d) and P_b is not the same, despite your intentions.

"Definition 4" is missing some detail.

There is a difference between "gaps" or "zones" or "rectangles" and "walls" or "nodes" that you aren't seeming to be utilizing as yet. The root of the tree is a line, not a zone.

Your fig 1 misses an important point -- not all rectangles/zones/gaps are infinite in one direction. In fact, had you recursed one more time it would show up -- but you stop at depth 3 in every case in fig 1. This makes it pretty non-representative.

Each zone has 4 edges. There are 4 starting edges "at infinity". New edges are spawned. When an edge is spawned, it divides the space into two zones -- each of which use the existing edges of the parent of the edge's zone, replacing one of their edges (opposite ones) with the new edge.

Ie.

Parent Zone spawns New Edge that is either Horizontal or Vertical. This also creates two Child Zones, which we call High and Low.

Parent Zone has 4 edges (top/bottom left/right) in two orientations (Horizontal and Vertical). We'll call the elements of each orientation pair "high" and "low" edges.

High Child has Edges that equal Parent Zone edge, except Parent Zone[(New Edge).Orientation].Low, which equals New Edge.
Low Child has Edges that equal Parent Zone edge, except Parent Zone[(New Edge).Orientation].High, which equals New Edge.

This difference -- between Zones and Edges -- seems to me to be simpler than talking about only Nodes -- because, really, the Nodes that are almost-but-not-quite adjacent to you don't seem that useful?

In practice, you want to be able to find the Zones near your Magnitude that are "near you" -- is your Node system an attempt at that? (Ie, you take your ancestor nodes, and the ones next to them, and from that you can find all of the near-same size Nodes adjacent to you?)

...

This is also what defines the uniform distribution as the worst-case scenario for the kd-tree, since it is unable to utilize any of its algorithmic optimizations. Since a quadtree‟s best-case scenario is a uniform distribution [6], this means that the worst case scenario for a kd-tree is (approximately) the best case for a quadtree.

That is a pretty strong statement.

...

Your O notation isn't dropping lower-order terms when you can?

...

B then provides a measure of how unbalanced the tree is, and by comparing it with a threshold value, we can then decide when the tree should be rebalanced, replacing all calls to the rebalance function in Insertion, Deletion and Move with a balance check.

Where is your argument that this doesn't devolve to a pathological case? Or is this just a heuristic optimization that you hope works?

...

I took at look at "B.1 SENTINEL NODE ANCESTORS", and the code never sets parent B?

...

More precisely, when we have determined that an image falls through to a child node, and that node does not exist, then the node must be created with a divider that passes through the exact center of the image that is being inserted, preventing redundant node creation.

Why? Why not just have the node with no divider?

...

The average location based NODE SPLITTING technique seems strange to me. The point of node splitting is to not have to iterate over as many images when you are doing collision detection. Why not pick your split in such a way that it, you know, splits the images into sets? (ie, at least one, and ideally both, of your children should have a significantly reduced number of elements).

If you define "significantly reduced number of images" properly (going from 1000 images to 999 may not be significant, while going from 2 to 1 might be), you could end up with a definition of "clumpy" (ie, all the images stacked on top of each other) that is rigorous, and show that your tree has performance characteristics that are a function of how "clumpy" the data is (for the purpose of culling, moving, deleting, inserting, etc). And you wouldn't have what looks like a hand-wavy system to split your regions (but maybe I misunderstand it?)

Are you trying to argue in NODE SPLITTING that a simple average of the average location of an image is sufficiently optimal for this task? That seems wrong.

Oh, equation (3) is on crack. That isn't what you want to optimize. A skinny image is very different than a 'fat' image in how it impacts the ideal splitting of a region. Ok, so (assuming "right to left" positioning of your edge) if your I_k was the right side, then fat and skinny work differently. But this doesn't punish you for "splitting" an element at all...

Ie, imagine you have this:

Code: Select all

` [------] <- A   [----] <- B       [-------] <- C            [---------------] <- D           [----------------] <- E           [----------------] <- F           [----------------] <- G`

it would be better to cut C in half by stopping after A/B than to continue to C. In fact, by advancing to include C in the left hand, you increase left's "contained elements" by 1 and drop right by 4 elements!

This looks like where you assumed this wasn't the case: (since increasing one would then therefore decrease the other below its maximum)

Ie, an increase of one by 4 could consist of dropping the other by a mere 1, or vice versa.

Then again, maybe I'm not understanding?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

blackhole
Posts: 4
Joined: Thu Jan 20, 2011 9:32 am UTC

### Re: 2D Culling with Regional KD-trees

I chose the division algorithm as a simple average because it has to be crazy fast, not necessarily particularly accurate. I did consider the exact case you have mentioned, but I can't come up with any algorithm that properly divides the nodes without sorting them or going through all the images every single time in a relatively expensive operation that is, at a minimum, O(n log(n)) The advantage to the average position is that its solution can be cached, resulting in O(1) time, as opposed to say, O(n) time every time an image was inserted, meaning for n image insertions thats O(n²) which is absolutely horrible. I specifically mention that it could be possible to improve the algorithm, but I simply can't come up with anything better that's not prohibitively expensive. If you know of a superior algorithm that can accurately subdivide in that case without, as you mentioned, devolving into a pathological case, I'd love to hear about it. In my experience, however, the division algorithm doesn't actually have to be very accurate at all. Losing those four images, in practice, really isn't much of a problem. You lose way more performance to images lying on the root division line that are by necessity never culled.

I'm sorry, I write these papers from the perspective of an engineer, not a mathematician.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: 2D Culling with Regional KD-trees

Meh -- an engineering solution that admits arbitrary bad behavior cases is a Tacoma Narrows solution.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

blackhole
Posts: 4
Joined: Thu Jan 20, 2011 9:32 am UTC

### Re: 2D Culling with Regional KD-trees

A Tacoma Narrows solution is better then no solution at all xP

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

### Re: 2D Culling with Regional KD-trees

blackhole wrote:A Tacoma Narrows solution is better then no solution at all xP

This statement sounds really irresponsible if you take it out of context of the problem at hand.