AW's kd-tree

Jump to navigation Jump to search
Revision as of 11 October 2013 at 18:45.
The highlighted comment was created in this revision.

AW's kd-tree

how fast is Andrew Wells kd-tree

    Tmservo (talk)‎13:17, 8 October 2013

    How Fast Is Andrew Wells KD-TREE

      Tmservo (talk)‎23:33, 10 October 2013

      I suggest you stop worrying about how fast a particular kd-tree is and just use one of them. The top few kd-trees are all very similar in performance and I am sure each have their pro's and cons. I personally still use Rednaxela's Gen 2 tree because of how self contained it is (vs his Gen 3 which has more structure).

        Chase‎06:10, 11 October 2013
         
        Edited by author.
        Last edit: 20:43, 11 October 2013

        If you were using it for Robocode I don't think you'd be worrying about which one. What are you using the tree for?

          Skilgannon (talk)‎18:27, 11 October 2013

          The tree that I have, is approximately as fast as rednaxela's 2nd gen. (slightly faster in my tests). Are you trying to write a kd-tree or just looking for one to use? As far as I know, jk's tree, rednaxela's tree, and my tree are all quite similar. Bucket kd-tree. No recursive search methods. Use a MBR (minimum bounding rectangle). Use a heap to store the points. I think rednaxela was the first to introduce most of those ideas to robocode, but in my tests, mine was slightly faster and presumable the same can be said of JK's tests.

            AW (talk)‎20:35, 11 October 2013

            there is no kd-tree at http://robowiki.net/wiki/User:AW/kD-Tree

              Tmservo (talk)‎20:45, 11 October 2013
               
               
               
               
              Retrieved from "http://robowiki.net/wiki/Thread:User_talk:Tmservo/gilgalad%27s_kd-tree"