Fractal Dimension Computation in Python Code

[Mike Brenner]

Myk> ... Has anyone got a fast routine for calculating the fractal
dimension of a set of points in 2 or 3D space?  Thanks.

According to the inventor of fractals (Hausdorff in the year 1899), you
can place the set of 2D points next to a wall and shine light through
them, and the fractal dimension is the percentage of shadow on the wall. 

If the points are not dense anywhere, then the fractional dimension will
be zero. But if parts of them are filled in, then they will cast a
shadow.

Same with the 3D points, just put them next to a four dimensional wall
and shine a four dimensional light through them (the way you measure the
amount of holes in a Swiss Cheese :).

To do this in Python, you would have to define "dense" as being points
that are within a certain distance of each other according to some
cohesion metric, and then add up all the parts according to their
topological coupling. The algorithm in outline would be something like
this:
   
	dimension=2
	total_area = point_set.integrate_area(dimension,metric)
	area = 0
	coupling = neural_net.cluster(point_set,dimension,metric)
	for connected_part in coupling:
		area = area + connected_part.integrate_area(dimension,metric)
	fractional_dimension = dimension * (total_area - area) / total_area

To make this work for real, just program the three missing functions:

	METRIC 		computes the distance between two points

	INTEGRATE_AREA 	integrates over point sets to get their area

	CLUSTER 	divides the set into independent connected point sets

If you don't have a neural net available to do the clustering, you can
use a genetic algorithm or an annealing algorithm, all of which are
equivalent. 

You could do this in an analog fashion by using a CRT projector onto the
wall of a dark room and a sensitive light meter feeding into a ADC
connected to your RS-232 or parallel or IEEE or Firewire port. Draw the
point set on the screen and have the computer read the light meter, then
draw an all white screen and read the light meter again, and take the
ratio. Here is the code:

	graphics.init()
	graphics.open()
	dimension = 2
	graphics.fill_screen(black)
	black_area = firewire.read_ADC_voltage()
	graphics.fill_screen(white)
	white_area = firewire.read_ADC_voltage()
	for point in point_set:
		graphics.draw_point(point,black)
	area = firewire.read_ADC_voltage()
	denominator = white_area - black_area
	numerator = area - black_area
	fractional_dimension = dimension * numerator - denominator

This code requires you install a graphic capability, a firewire
capability, a light sensitive meter, an analog-to-digital converter, a
firewire driver for the ADC. To do a 3D point set this way, would
probably involve techniques such as a tomograph machine to do one slice
at a time.

Mike Brenner
MikeTheMathematician at IEEE.org