Fractal Dimension Computation in Python Code

[Andrew Kuchling]

A Google search on "calculating the fractal dimension of a set of
points" turns up lots of pointers.  What about a procedure like the
one described at http://hypertextbook.com/chaos/33.shtml?

1) Choose a number of sizes h1, h2, ...
2) for h in h1, h2, ...:
     Divide the 2D or 3D region into little boxes of size h.  
     Count how many boxes contain a data point, and call it N(h)
3) Plot N(h) on a logarithmic scale and measure the slope of the line, which
   will be the fractal dimension. 

I'm not sure how to make step 2 fast, though.  Perhaps you could loop
over each data point, figure out what box it falls in, and scan
through the other points eliminating any that would fall into the same
box.  That would be O(n**2) for n data points.

<think think>  

Or, loop over the data point and compute the box coordinates (x,y) for
each point, storing it (O(n)).  Sort the list of (x,y) coordinates
(O(n lg n)) and then eliminate any duplicates (O(n)); N(h) is the
number of unique coordinates.  O(n lg n) running time.  Or just store
each (x,y) coordinate in a dictionary; N(h) == len(dictionary) when
it's done.  That should be just O(n), one pass to compute (x,y) and
then a len().

--amk