Yumf

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

Algorithm fixed

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

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:

• Wikipedia:Image use policy
• Wikipedia:Image copyright tags

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)

Notification of automated file description generation

Your upload of File:Bin computational geometry.png or contribution to its description is noted, and thanks (even if belatedly) for your contribution. In order to help make better use of the media, an attempt has been made by an automated process to identify and add certain information to the media's description page.

This notification is placed on your talk page because a bot has identified you either as the uploader of the file, or as a contributor to its metadata. It would be appreciated if you could carefully review the information the bot added. To opt out of these notifications, please follow the instructions here. Thanks! Message delivered by Theo's Little Bot (opt-out) 13:32, 8 February 2014 (UTC)