Re: [Algorithms] procedural star graph generator

[Fabian G. <ry...@gm...>]

On 10.09.2011 01:23, Tom Sparks wrote:
>> Sent: Saturday, 10 September 2011 3:49 AM
>> Subject: Re: [Algorithms] procedural star graph generator
>>
>>
>> I think you need to define which interpretation of "star graph" you actually mean.
>>
>>
>> Graph theory, or astronomy?
> graph theory Not astronomy sorry
>
> I've been do some reading and Cellular Texture seams like what I need but the example I've seen are texture-centric

The graph theoretic version of star graphs is trivial! You just have N 
vertices and N-1 edges. One vertex is in the "center" (suppose without 
loss of generality it's the first one) and then the edges are {1,i} with 
2 <= i <= N. "Procedurally generating" such a graph is a single for loop!

Considering your reference to cellular textures, what you probably mean 
are Voronoi diagrams:

   http://en.wikipedia.org/wiki/Voronoi_diagram

If so, there's (reasonably well-known) algorithms for generating it from 
a set of points. The complexity of both the algorithms and 
implementation depends considerably on your requirements; if you just 
need a solution for a low number of points in the plane, that can be 
done with relatively little code. Higher dimensions require more work, 
and algorithms with optimal O(n log n) complexity (this is a lower bound 
for the complexity of algorithms that determine planar Voronoi 
diagrams!) are more involved than O(n^2) or worse algorithms.

-Fabian