[Date Index] [Thread Index] [Author Index]

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