Talk:Voronoi diagram

From Wikipedia, the free encyclopedia

This is the dual to delaunay triangulation, isn't it? Chas zzz brown 10:37 Feb 2, 2003 (UTC)

Correct --- and that article is even stubbier than this one. Maybe I'll work on both of them further at some point. Michael Hardy 22:28 Feb 5, 2003 (UTC)

Another Example is the Wigner-Seitz cell in materials science.--149.220.16.110 15:30, 15 September 2006 (UTC)


Is it true that John Snow used a Voronoi diagram to illustrate his investigation of the cholera epidemic? I've seen some of his maps, and don't recall seeing a Voronoi diagram (or even an approximation to one) on any of them. Gareth McCaughan 00:24, 2005 Apr 10 (UTC)

See Figure 12.6 at [1]. The text explains that Snow plotted a line that was equidistant between the Broad Street pump and alternative pumps, so I think it qualifies as a simple Voronoi diagram. Gandalf61 07:48, Apr 11, 2005 (UTC)

Aha. The Voronoi line wasn't present in Snow's map in On the mode of communication of cholera (1854), which is the famous one reproduced in a million different places. It's there in his report to the Cholera Inquiry Committee in 1855. I agree that it qualifies as a simple Voronoi diagram. Perhaps a link to http://www.epi.msu.edu/johnsnow/Snow%20pub%20doc/CIC-JSRpt_SF12.htm (his CIC report), or to the page you mentioned above, should go in the References? Gareth McCaughan 09:12, 2005 Apr 11 (UTC)


Contents

[edit] Artwork; unusual statements

This article already has some nice graphics; are we sure its a good idea to also add ascii art to this? I don't think so ...

Also: there's talk about a rectangular tesllation with points "not at the center" ... how can that be? its a metric polygon; is this a subtle statement that the center of mass doesn't align with the metric center? Besides the "center of mass", there are other types of "centers" e.g. center for diffusion processes, etc. How about other definitions of "center"?

Also, for a rectangular array, the voronoi cell is not a rectangle any more ... so the "examples" section has several confusions in it ... ditto for the remarks about isocleles trinagles ... linas 20:28, 26 July 2005 (UTC)

[edit] Algorithms?

How about adding some mention of the algorithms used to calculate a voronoi diagram? IIRC, there is one that works in O(n*log(n))?

If you can describe such algoritms accurately, then please add them. linas 16:07, 23 November 2005 (UTC)

[edit] pronunciation?

Voronoi appears to be of Ukranian descent.--MinorEdits 08:45, 1 June 2006 (UTC)

[edit] Additional Material to Consider for Uses and Application

"Spatial Query Processing Utilizing Voronoi Diagrams" from the Google TechTalks series: http://video.google.com/videoplay?docid=-2755539754474649930

[edit] Non mathy?

The concept behind Voronoi Diagrams can be explained in non mathematical terms/notation (ok, you need points, lines and distance, but not much more then that). With the help of a picture, shouldn't that sort of explanation be in the introductory blurb?

Also, it would be interesting to know what "human algorithms" were used to draw 2D voronoi diagrams back before computers.

[edit] Fermat point

If you have just three points do you get the Fermat point? --Salix alba (talk) 22:22, 24 September 2007 (UTC)

Nope. The Voronoi point is the intersection of orthogonal bisectors, i.e., of lines perpendicular to the sides of the triangle pasing through their middles. So you may easily prove that it will be the Fermat point only for an equilateral triangle.`'Míkka 06:24, 25 September 2007 (UTC)
It is the circumcenter, though. We could say, in the properties section, that the mutual boundary point shared by any three adjacent points is their circumcenter. PhiloMath (talk) 16:39, 10 December 2007 (UTC)

[edit] Software

I deleted the software section, since there is really a lot of software that can do it and I don't think we should be in the business of plugging a particular package. If you do add it back, I would like to see, eg, qhull mentioned. --Dylan Thurston 17:43, 1 October 2007 (UTC)

[edit] Algorithm?

An easy algorithm for creating a Voronoi diagram would seem to be, for each pair of points, to draw a line between them, and then to draw a boundary perpendicular to that line, crossing it at its exact centre. The segments created by these boundaries then make up the cells in the Voronoi diagram. But what happens if this algorithm creates segments without a point inside them? JIP | Talk 13:47, 8 October 2007 (UTC)

You could take the set of perpendicular bisectors, which will form a super set of the Voronoi diagram, And then search for those segments which form a polygon around each vertex. Whether this will be efficient is a good question and there has been a lot of work on efficient algorithms. In practice I'd recommend the Qhull program (see links) which works by computing a convex hull in n-dimensions. --Salix alba (talk) 15:40, 8 October 2007 (UTC)
Delaunay triangulation (the dual problem) has some more details of algorithms. --Salix alba (talk) 16:11, 8 October 2007 (UTC)

[edit] Space complexity mentioned in the Generalizations section

It's mentioned in the generalizations section that it requires at least O(n^floor(d/2)) space for a Voronoi diagram in d dimensions. This doesn't really make sense, though, just because you don't want to use big-Oh here, but rather omega, I think. If you use big-oh, you're saying "it takes less than X space, which is too much!" since big-oh is basically a <= or < type inequality, depending on case, whereas omega is > or >=.

Also, it doesn't really make sense to say any dimension above 2 is out of the question. You could probably say instead that it doesn't make sense for d > > 2, or for "large d" (for d=3 it is not so bad, for non-gigantic point sets). PhiloMath (talk) 16:45, 10 December 2007 (UTC)