David. You're awesome. Thanks for these excellent ideas and resources. Finally -- a use for my undergrad mathematics degree... ;)
Time to knock off the rust. I'll definitely send out the link when I have it working (or alternatively, when I have something to show). -Steve --- In svg-developers@yahoogroups.com, "ddailey" <[EMAIL PROTECTED]> wrote: > > Hi Steve, > > Looking at the picture you've provided suggests to me the following approach: > > a) generate a Voronoi diagram [1] (I think this can be done quickly, i.e. in less than O(n^2) ) on a random set of n points; though I've never actually done it -- maybe somebody knows of a link to an SVG that does that already??; > b) while generating, keep track of the edges (since these provide the incidence matrix of the graph); > c) within each polygon, inscribe a circle -- inscribing a circle inside a convex polygon should be fairly easy it seems > > Whether the Voronoi diagrams would be representative of the set of all convex tessellations of the plane relevant to your purposes or not, I'm not sure. Alternative pseudo-random tessellations could be considered with domino tilings, rhombic tilings, or other nonperiodic tilings. > > That's probably how I'd try to do it. > > Alternative ways of approaching it would be to generate quasi 2- Euclidean graphs (as in [2]) (in which adjacency of nodes is based on a threshold of their 2-D Euclidean positions, followed by elimination of crossing lines); followed by expansion of circles until the radius equals half the distance of the nearest neighbor. > > Harary, I think, has a theorem of some sort establishing the number of distinct triangulations of a planar region -- one such triangulation could be induced upon a plane filled with n random points and from there the geometric dual would be something like a Voronoi diagram, it seems. > > holler when you get it done, since it'd be fun to see > David > > [1] http://en.wikipedia.org/wiki/Voronoi_diagram > [2] http://srufaculty.sru.edu/david.dailey/svg/graphs30.svg > ------------------------------------ ----- To unsubscribe send a message to: [EMAIL PROTECTED] -or- visit http://groups.yahoo.com/group/svg-developers and click "edit my membership" ----Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/svg-developers/ <*> Your email settings: Individual Email | Traditional <*> To change settings online go to: http://groups.yahoo.com/group/svg-developers/join (Yahoo! ID required) <*> To change settings via email: mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] <*> To unsubscribe from this group, send an email to: [EMAIL PROTECTED] <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/
