create a "worst-case" tree type to test algorithms with

[rcurtin]

Reported by rcurtin on 30 Jun 43353975 16:03 UTC
In the paper 'Tree-Independent Dual-Tree Algorithms' (http://arxiv.org/abs/1304.4327) the general definitions for a space tree are laid out. All of the dual-tree algorithms are written in the generalized format detailed in the paper (or, well... they should be converted...). However, I'm nearly certain that the algorithms, as implemented, won't work for any arbitrary space tree type.

So, we should make some kind of space tree which is meant to test these algorithms (keep in mind it is not meant to perform the algorithm quickly).

I think it should maybe look something like this:

• At the creation of each node, it is given a list of points which are going to be its descendants. It picks a random subset of these to be its own points, and then passes the rest of the points, plus maybe some of its own points, to its children. This way we get points that are in one level, but not the next, but then also in the one after that.
• The convex subsets represented by each node can (and maybe should) be overlapping.
• The way the convex subsets are expressed should not be dimension-specific. Maybe some kind of n-gon which encloses the descendant points and where n is some random number that is different at each node.
• Some child nodes should be identical copies of the parent node.

Then, if this is implemented, we will almost certainly find that our dual-tree algorithms, as implemented, don't always work with any type of space tree.

Migrated-From: http://trac.research.cc.gatech.edu/fastlab/ticket/282

[rcurtin]

I don't think this is worth the effort anymore.