Thursday, March 20, 2003

hi choesnah,
yes, I did work with Voronoi diagrams and Delaunay triangulations
(actually delaunay tetrahedralisations, since it was 3d). Unfortunatelly,
even if I did write a paper on my work it did not talk that much in detail
about Voronoi diagrams. You can anyway find it at:
it seems anyway not to be working that well so you can instead try:

for more information on voronoi diagrams there are quite a few applets
around in which the algorithms are explained. I used one that was an
Incremental algorithm. It basically goes like this:

(this is for 2D, for 3d, substitute where it says triangles by tetras, and
circles by spheres (and three points by four points).

you have points in space.

1.make three points that form a triangle that includes all the other points
(usually this is done by drawing a huge triangle, basically the biggest
one you can build. It will for shure include all your points.

2.calculate the circle that circunscribes the triangle (there are formulas
lying around in the net for this).

3. take any point (of the ones you had) and find out in which circle it lays
(if this is the first time, that is easy, since it will lie in the huge
triangle and therefore circle you defined).

4 make triangles form the new point to the three points that define the
circle it is in, and for each of the new triangles calculate their
circunscribing circle.

5.iterate for any next point from step 3.

You will obviously run through all the points untill you are done with
them. The triangulation you have will be one in which there are no points
that are inside circles defined by any other three points (Delaunay
triangulation). The dual of the triangulation is the Voronoi diagram.

Good link:

the algorithm I used was some code I adapted from Bowyer-Watson's
Incremental algorithm. The page I found it in does not seem to work

Do you know any C/C++ or Java? that will make it easier since most of the
algorithms you find around are writen in those languages (there are some
bits of Fortran code lying around, if you know Fortran).

There is somethin called Qhull (it is an open source code for calculation
of convex hulls, delaunay triangulations and voronoi diagrams to n
dimensions!) but I found difficult to find my way around it and the

Often nice people leaves the code for their applets accessible in their
pages. Check in the html code the tag "code" for the applet (it will say
something.something.class or something.class check in your browser for a
file in the same directory called the same, but instead of class write
.java, you may be lucky and get the code! (if you know C++ it will be
quite easy to translate the code).

The best thing to do is to give yourself a couple of weeks to surf, colect
info and analise the algorithms.

Good luck and say hello to Paul and Christian.


- - - - - - - - - -

I think that what you are discussing here is the status of the observer, and
of course in a simulation there is this problem with getting the various
levels of observation from local to global sorted out, so that as in starlogo
we can be explicit about it.

this problem doesnt occur in the world since the status of the observer is an
emergent property of the evolution of perceptive structures. I dont have a
problem with the idea that there is some circularity involved, structural
coupling has to be reflexive - its the old boot strap problem - the need for
a primum mobilus (first mover) which seems a problem when considering
classical machines, but pulling yourself up by your own bootstraps is exactly
what life has to do. maturana is very careful to avoid tautology, but his
circular way of reasoning is needed so as not to go into infinite regress.

I dont know who we were talking about, but of course i would always disagree
about the necessity for a designer. thats what the blind watchmaker is all
about. the very idea of a "designer" is anathema in the context of evolution.
of course as i said above, in the context of simulation we have to design the
system, so what we have to do is
1. be very explicit about the stuff that is designed and define the axioms
very carefully
2. try to get away with the minimum of arbitrary rules
3. be explicit about the different sorts of observers in the system

self organisation does i guess depend on certain space time physics stuff.
there is a new book out which i read about (cant remember name of course)
which explains that nature has many underlying regularities based on least
energy lattices and standard valencies among atoms and molecules. so when an
organism develops bilateral symmetry or segmentation it is not some one off
lucky chance at all, but an inescapable outcome of those underlying laws of

if we lived in a universe where pi was an integer, then presumably we would
find different regularities emerging.