User:AW/Kd-Tree/thoughts

From Robowiki
< User:AW
Revision as of 01:56, 14 March 2011 by AW (talk | contribs) (Created page with 'I was thinking about how to write a kd-tree and I think that none of the ones I have seen are 100% accurate. For example assume a 2 dimensional space which for convenience will …')
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

I was thinking about how to write a kd-tree and I think that none of the ones I have seen are 100% accurate. For example assume a 2 dimensional space which for convenience will be a the refered to by the cartesian coordinate system ({x | 0 < x < 1} {y | 0 < y < 1}). Suppose we had these points added in this order and the tree was partitioned with one point in each node (if you don't understand / I described this incorrectly, please see: Spatial Index Demos).

1) point one: (0.5, 0.8)

2) point two: (0.45, 0.5)

at this point the data is partitioned (ie. the graph is divided by the line x = 0.5)

3) point three: (0.55, 0.45)

point three is closer to point two than it is to point one, but the kd-tree will say the closest match is point one. The proper way to do partition this would look more like a voronoi diagram, but this would make the trees slower.

Am I right?

--AW 00:56, 14 March 2011 (UTC)

Retrieved from "http://robowiki.net/w/index.php?title=User:AW/Kd-Tree/thoughts&oldid=18735"