RE: Mathematica Code to Build and Access KD Trees
- To: mathgroup at smc.vnet.net
- Subject: [mg45872] RE: [mg45713] Mathematica Code to Build and Access KD Trees
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Wed, 28 Jan 2004 05:19:10 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: Richard Palmer [mailto:dickp at bellatlantic.net] To: mathgroup at smc.vnet.net >Sent: Wednesday, January 21, 2004 10:55 AM >To: mathgroup at smc.vnet.net >Subject: [mg45872] [mg45713] Mathematica Code to Build and Access KD Trees > > >Anybody know where some published code exists. >-- > > Some code, hm, you must be joking! There are many different flavors of k-d trees, much depending on the application. In my private library I find something in - G.H.Gonnet: Handbook of algorithms and Data Structures, 1st ed. 1984 - Robert Sedgewick: Algorithms (there are quite a lot versions out now, I have the oldest one from 1983, with coding in Pascal) - Steven S.Skiena: The Algorithm Design Manual, 1998 Gonnet and Skiena give you pointers to the literature. There also is something to be found at the WRI site: http://library.wolfram.com/infocenter/MathSource/462/ But this is only a study of an original algorithm as given by J.L.Bently (ACM Transactions, Vol.3 No.3, 1977) using Mathematica as a rapid prototyping language. For production purpose it's useless. Dealing with functional data structures (and keep performance) is not easy. Perhaps you might like to look at Jens-Peer Kuska's contribution to this newsgroup http://forums.wolfram.com/mathgroup/archive/2000/Apr/msg00304.html and also at my response to it http://forums.wolfram.com/mathgroup/archive/2000/Apr/msg00424.html The example there is for OctTrees, but similar principles also apply to kd-trees in Mathematica. If you want to study problems of that kind, look into - Chris Okasaki: Purely Functional Data Structures, 1998 (this is for ML and Haskell) However, if you intend to do more than a toy application you preferably should code in C or buy or steal a library. If you want to get reasonable help with Mathematica coding, however, you must show more from your application problem, and show your tries, i.e. give a challenge to the community. Your quest doesn't. -- Hartmut Wolf