Hi

I just wanted to let know the people using a quadtree datastructure that

I

set up a web site containing C++ source code, man pages and

documentation

for a linear quadtree. The nice thing about this quadtree is that the

nodes can

be browsed in constant time, namely, each move in the quadtree has the

exact

computational cost of ONE addition. Any traversal of the nodes can be

implemented, for ex. I solved the coplanarity problem of hierarchical

triangulation

in optimal computational time in

http://lcavwww.epfl.ch/~balmelli/downloads/vmv99.ps.gz

The code is very simple to use, the nodes are traversed with simple

function

like "goNorth", "goSouth"... any browsing can be implemented. The method

to

obtain the constant time property is described in

http://lcavwww.epfl.ch/~balmelli/downloads/quadtree.ps.gz

I use the quadtree in computer graphics to store hierarchical meshes

built on terrain

data. The quadtree is also very useful in image processing, compression,

digital signal processing.

The quadtree is organized as A SPATIAL DATASTRUCTURE, which makes it

very

useful to store such kind of spatially organized data.

Download the code on the website and register! I am not representing a

company, i'm

only a phd student, so your email will not be used for any commercial

purpose. :)))

Registered people will receive update of code, and a soon-to-come Java

applet

demonstrating the quadtree usage. The website is at

http://lcavwww.epfl.ch/~balmelli/software/quadtree/index.html

enjoy, any comments are welcome!

all the best,

Laurent Balmelli

Ecole Polytechnique Federal de Lausanne