MathGroup Archive 2004

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

Search the Archive

RE: Mathematica Code to Build and Access KD Trees

  • To: mathgroup at
  • Subject: [mg45872] RE: [mg45713] Mathematica Code to Build and Access KD Trees
  • From: "Wolf, Hartmut" <Hartmut.Wolf at>
  • Date: Wed, 28 Jan 2004 05:19:10 -0500 (EST)
  • Sender: owner-wri-mathgroup at

>-----Original Message-----
>From: Richard Palmer [mailto:dickp at]
To: mathgroup at
>Sent: Wednesday, January 21, 2004 10:55 AM
>To: mathgroup at
>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

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:

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

and also at my response to it

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

- 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

  • Prev by Date: Re: RealDigits bug?
  • Next by Date: Re: Noisy data and ListConvolve
  • Previous by thread: Mathematica Code to Build and Access KD Trees
  • Next by thread: RE: Mathematica Code to Build and Access KD Trees