User talk:Yumf

From Wikipedia, the free encyclopedia

Please look carefully at the algorithm:

function query (rectangle r, kd-tree node n) {

  var axis := n.axis;
  var median := n.median;
  if median > r.interval[axis].low then
   return query(r, n.left);
  if median < r.interval[axis].high then
   return query(r, n.right);
  if median in r.interval[axis] then
   output n.point;

}


rectangle r = [(-1,-1) (1,1)]

Now suppose that the kd-tree only has one node, (0,0), which obviously is in the interval. The code above fails because on the first call:

axis = 0 median = 0 r.interval[axis].low == -1

thus, median > r.interval[axis].low == true

a) If you interpret the return statement as it is usually semantically defined in all programming languages then it checks the left subtree, which is empty, and returns an empty list (i.e. outputs nothing).

b) if you remove the return statements then you are only checking one axis and you can easily find an example in which the wrong point is output.

I think that this algorithm, as it is written, is wrong. If I am wrong in some assumption, please explain.

Thanks, Uranor

[edit] Algorithm fixed

Thanks for pointing out the bug. I've updated the page with the fix.

[edit] License tagging for Image:Bin computational geometry.png

Thanks for uploading Image:Bin computational geometry.png. Wikipedia gets thousands of images uploaded every day, and in order to verify that the images can be legally used on Wikipedia, the source and copyright status must be indicated. Images need to have an image tag applied to the image description page indicating the copyright status of the image. This uniform and easy-to-understand method of indicating the license status allows potential re-users of the images to know what they are allowed to do with the images.

For more information on using images, see the following pages:

This is an automated notice by OrphanBot. If you need help on selecting a tag to use, or in adding the tag to the image description, feel free to post a message at Wikipedia:Media copyright questions. 23:06, 16 October 2007 (UTC)