Talk:Voronoi diagram

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Importance
 Field: Geometry

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)

It might be helpful to talk about the order of a voronoi diagram. E.g. something along the lines of, "a Voronoi cell can be generated from a set of points from S. The cardinality of this set is referred as as the order of the Voronoi diagram". It might also help to give algorithms for constructing order-k diagrams and the complexity of generating an order-k diagram. —Preceding unsigned comment added by Sunupsundown (talkcontribs) 19:45, 1 October 2008 (UTC)

Artwork; unusual statements[edit]

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)

Algorithms?[edit]

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)

pronunciation?[edit]

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

Additional Material to Consider for Uses and Application[edit]

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

Non mathy?[edit]

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.

A non-mathy observation: doesn't the Voronoi iteration explain the approximate cultural and sometimes political boundaries for countries with land borders adjacent to others? That is, the farther from the capital, the weaker the influence. A real world example like this would be useful. —Preceding unsigned comment added by Bobbyleeds (talkcontribs) 15:45, 13 August 2010 (UTC)

I did a quick Google search for this. I couldn't find a national-level example, but I did find an example for the states of the USA. Not sure how (or whether) to include it in the page though. The applications is already a bit messy... Warrickball (talk) 10:23, 22 August 2011 (UTC)

This article assumes one is familiar with terminology and even goes to obnoxious lengths to introduce it when it's not necessary. In other words: this article has been written by a group of insufferable twits. Speedy deletion.— Preceding unsigned comment added by 82.249.88.27 (talkcontribs) 29 October 2012‎

I've removed the incomplete WP:AFD nomination of the article. From the above comment its clear you ment the nom more as a protest rather than an actual case for deletion.--Salix (talk): 09:28, 29 October 2012 (UTC)
I've simplified the lead section which should make it a little simpler.--Salix (talk): 09:45, 29 October 2012 (UTC)

Fermat point[edit]

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)

Software[edit]

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)

Algorithm?[edit]

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)

Space complexity mentioned in the Generalizations section[edit]

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 >=.

They may not have lower bounds on the running time for all higher dimensions, but believe that the bounds are tight. In 3D, however, the worst-case bounds are known to be both O(n^2) and Omega(n^2) (i.e. Theta(n^2)), see http://www.math.tau.ac.il/~michas/wads95.pdf. If they only give big-Oh, that usually means that its the best worst case upper bound known, and may be achievable by some inputs. So O(n^2) is also O(n^3), but if you knew an algorithm was O(n^2), you would say that and not O(n^3) so that it is known that as far as we know it could take up to quadratic space but never requires cubic-space. --128.119.40.196 (talk) 16:05, 9 July 2013 (UTC)

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)

I am actually not convinced with the expression itself. With the given formula, it is O(n^2) for d=3. This means that if I have 1000000 points and I add one more, the increase in the required space will be proportional to 1000000. On the other hand the graph will be effected only locally, so why would I need ~1000000 extra bytes to represent that. It is actually further in question since a set of points define a unique vronoi diagram, just storing those points in itself is a way of storage and this has O(n) complexity. Therefore the storage implementation is also a factor and it should be stated. I'm not an expert on the area, so what I say might be complete nonsense, but I still think that part begs a citation. I've checked the reference about space efficient representation, and it doesn't say much about the expression in question. Enisbayramoglu (talk) 12:45, 16 March 2009 (UTC)

I haven't looked into this, but it may just be the best upper bound we can prove. Clearly adding a single point can effect all the other voronoi cells. A pathalogical example, place all of your 1,000,000 points along the x-axis at the integers 1, ..., 1,000,000. Then your VD is made up of exactly 1,000,000 planes, each orthogonal to the x-axis at positions 0.5, 1.5, 2.5, ... Now add a single point somewhere like (500,000, 500,000, 500,000). I believe this will require each of the original 1,000,000 Voronoi cells to have a new facet added (and thus add 1,000,000 facets to the VD). Tight bounds are proven here: http://www.pi6.fernuni-hagen.de/publ/tr277.pdf--128.119.40.196 (talk) 15:50, 9 July 2013 (UTC)
Here: http://cstheory.stackexchange.com/questions/17331/outer-part-of-voronoi-diagram-in-3d in the solutions two point sets are described which require Omega(n^2) in 3D.

Discrete set of points?[edit]

In the Definition section of the other article it claims that "For any (topologically) discrete set S of points in Euclidean space and for almost any point x, there is one point of S closest to x". This is untrue as shown by the example in the Discrete space page {1, 1/2, 1/4, ...} using the usual euclidean metric: Any negative number has no closest point in the set. It seems to me that some additional restriction like "no accumulation points" is required. TomC phys (talk) 02:28, 12 February 2009 (UTC)

Actually, S just needs to include all it's limit points. Including 0 in your example fixes it with no problems. Nekura (talk) 03:03, 25 June 2009 (UTC)
Thinking more about it, is it really a requirement, or does it just make the diagram look nicer? The original definition starts with finite sets, so "closest point" could be defined for every point c in the space. But is it "required" that every point c have a closest point, or is it just a relic from the finite case? Is it the set of points in the space, or the set of cells associated with each point in S? Nekura (talk) 03:54, 25 June 2009 (UTC)

Question about existence[edit]

If I have a general graph consisting in a set of points and links among them, can I associate to it a "triangulation" in some sense? I mean, regarding the graph as a Voronoi dual to the former triangulation. If yes, can I do it for any d-dimensional generalization of triangle cells or are there requirements to fulfill? I'd like if someone is able to point me out an answer and eventually a reference. I'm posting this question also in Delaunay's triangulation page. Omar.zanusso (talk) 10:33, 5 March 2009 (UTC)

Conflict between Introduction and Definition[edit]

In the introduction, a Voronoi diagram is defined as a decomposition of a metric space (any), but in the "Definition" section, it is spoken only of Voronoi diagrams in Euclidean spaces. 00:29, 19 June 2009 (UTC)

Also it should be a clarification between the general definition of Voronoi diagrams (i.e., of any order and within any metric) and the usually known as "Voronoi diagram" that refers to a first-order Voronoi diagram in euclidean space. --RedBlackTreeNode (talk) 07:20, 30 September 2011 (UTC)

Weighted Voronoi Diagrams[edit]

I'm looking for information on weighted Voronoi diagram. Google only gave me references to programs that do it. There should be a section on it, including the difference between Multiplicative and Additive. Nekura (talk) 00:41, 25 June 2009 (UTC)

Here you are. - Altenmann >t 18:59, 26 June 2009 (UTC)


Higher-order Voronoi diagrams[edit]

This article says:

Although normal Voronoi cells are defined as the set of points closest to a single point in S, Nth-order Voronoi cells are defined as the set of points closest to n points in S. Higher-order Voronoi diagrams also subdivide space.
Higher-order Voronoi diagrams can be generated recursively. To generate the nth-order Voronoi diagram from set S, start with the (n − 1)th-order diagram and replace each cell generated by X = {x1x2, ..., xn−1} with a Voronoi diagram generated on the set S − X.

I find this quite unclear. How do you measure distance to a finite set of points? Is it the sum of the separate distances? If so, it should say so, and if not, it should say what it is.

Next, suppose I want to generate the 2nd-order Voronoi diagram. I have a set S of points and I draw their Voronoi diagram. I presume that's the "1st-order" Voronoi diagram. We have n = 2. So I am told to "start with the 1st-order Voronoi diagram and replace each cell generated by X = {x1} with a Voronoi diagram generated on the set S − X." Delete points one-at-a-time and draw separate Voronoi diagrams? And this tesselates space? This doesn't make sense. Michael Hardy (talk) 11:45, 11 August 2009 (UTC)


OK, I found this web page. It says two points are in the same nth-order Voronoi cell if they both have the same set of n nearest neighbors in S. That is clear. The text above says "closest to n points in S". That is utterly unclear: it requires us to measure the distance from a point to a set of n points in S, without saying whether that means a sum of separate distances or what. I don't understand why people write like that; it's just abusive to the reader. (Maybe changing capital N to lower-case n in mid-sentence should warn us that whoever typed this wasn't paying attention.) Michael Hardy (talk) 11:58, 11 August 2009 (UTC)

...the second paragraph is still unclear at best. Michael Hardy (talk) 11:59, 11 August 2009 (UTC)

Recently Added Link[edit]

The link which was recently added "V*-Diagram: A Highly efficient technique for processing moving nearest neighbor queries" seems to be an author referencing their person research which is related to Voronoi articles but clearly outside the scope of a general article on the subject. I will remove this link soon unless someone objects. RuppertsAlgorithm (talk) 01:23, 11 September 2010 (UTC)

WorldMap.pdf[edit]

New external link:

I downloaded this but see no content other than a caption. How about you? —Tamfang (talk) 01:47, 12 July 2012 (UTC)

real life voronoi[edit]

Interesting maps appeared on Reddits /r/mapporn including two real life maps of the US and world as a Voronoi diagram. They here and here. They should be added ASAP in my opinion rather than duplicating the one you have now. I hope it is changed but I do not know how to do so. 92.23.66.70 (talk) 15:37, 3 July 2013 (UTC)