Talk:Voronoi diagram
![]() | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
Dual to Delaunay triangulation?
[edit]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)
Wigner-Seitz cell
[edit]Another Example is the Wigner-Seitz cell in materials science.--149.220.16.110 15:30, 15 September 2006 (UTC)
John Snow's cholera map
[edit]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)
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
Order of a Voronoi diagram
[edit]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 (talk • contribs) 19:45, 1 October 2008 (UTC)
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 (talk • contribs) 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 (talk • contribs) 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 , 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 = {x1, x2, ..., 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)
Blank for me too. // NomadicVoxel (talk) 01:53, 4 July 2021 (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)
Dead link to Melbourne school zones
[edit]The site melbourneschoolzones.com has apparently shut down due to a price increase on the Google Maps API, and the version on archive.org doesn't really work without JS, suggest the link is removed, maybe along with the entire section as it's not very useful without the map. — Preceding unsigned comment added by 129.194.48.105 (talk) 10:45, 27 January 2020 (UTC)
Suggestion to simplify the first paragraph
[edit]The first paragraph feels kind of dense to me and I was about to edit it, but being new to the editor side of Wikipedia, I was unsure if I should actually submit it. Thoughts? "...or in other words, a Voronoi diagram is map shaded to indicate where the nearest significant point is from any location." — Preceding unsigned comment added by NomadicVoxel (talk • contribs) 07:07, 5 May 2020 (UTC)
What are "adjacent" points on a convex hull? Clarification is needed
[edit]The section Properties contains this passage:
"Assume the setting is the Euclidean plane and a discrete set of points is given. Then two points of the set are adjacent on the convex hull if and only if their Voronoi cells share an infinitely long side."
But what does it mean for two points of the set to be "adjacent on the convex hull" ???
I hope someone knowledgeable about this subject can clarify this for readers. 2601:200:C000:1A0:F447:6226:63A4:B204 (talk) 19:16, 11 May 2022 (UTC)
- What do you think it means for two vertices of a polygon to be adjacent? —David Eppstein (talk) 19:31, 11 May 2022 (UTC)
Information about the surface area of cells relevant?
[edit]Today, I made an addition to the page that was removed because it cites my article. I believe the suggested modification is interesting and pertinent enough to be included, but I acknowledge my strong bias and so I leave this issue to be resolved by the community. Thanks, Ryan. Ryancots (talk) 15:41, 28 December 2022 (UTC)
- I have a few concerns besides COI about your proposed edit. WP:PREPRINT for one. Also, this property sounds like it might be a property of any partition into convex sets with marked points, and not a special property of Voronoi partitions. I would also want the property to be described in a style similar to the other properties, and not in the style of a math paper. Eigenbra (talk) 17:45, 28 December 2022 (UTC)
- Great, thanks for checking out the edit, and thanks for your feedback. Ryancots (talk) 10:29, 29 December 2022 (UTC)
section
[edit]- In general, a cross section of a 3D Voronoi tessellation is not a 2D Voronoi tessellation itself, since the cells are all convex polyhedra.
Both parts of this statement are clearly true, but the applicability of "since" is not obvious to me. —Tamfang (talk) 03:07, 25 August 2023 (UTC)
- I agree. Edited to remove that clause entirely. Eigenbra (talk) 13:34, 25 August 2023 (UTC)
fundamental definition should be points in the Euclidean plane, not arbitrary metric spaces
[edit]This article uses an overly abstract definition that is rare in practice (by at least an order of magnitude I would guess) and overly technical for much of the intended audience. I think it should be refocused on the Euclidean plane case, with a more abstract / general definition deferred to a section about generalizations. Let me recommend a first paragraph along the lines of:
- In mathematics, a Voronoi diagram is a partition of the Euclidean plane into regions close to each of a given finite set of points (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer (at smaller distance) to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation. The concept of a Voronoi diagram has been generalized to use objects other than points as the seeds and to settings of higher dimension or more generally to arbitrary metric spaces with an alternative notion of distance.
This would then simplify much of the later presentation which repeatedly adds "in the Euclidean plane" or the like as a qualifier. –jacobolus (t) 20:10, 3 September 2023 (UTC)
I made a O(n) voronoi algorithm
[edit]One really simple O(n2) algorithm isn't described in this article. Here's the pseudocode:
Given n seeds in a plane: For each seed S(i) where i=0 to n-1 For each seed S(j) for j != i Generate an "infinite" half-plane with its boundary bisecting the line connecting S(i) and S(j), with the half-plane containing S(i). The "infinite" extent need be no bigger than the span of seeds. Perform a constructive solid geometry intersection operation with this half-plane and all previous half-planes generated in this loop end inner loop end outer loop
Does anyone know if this algorithm has a name that can be mentioned in the article?
This algorithm results in voronoi polygons around each seed. It's an O(n2) algorithm and I'm surprised it isn't mentioned here due to its simplicity and ease of understanding. The intersection of multiple half-planes at different orientations always results in a convex polygons around a seed that corresponds to a voronoi polygon.
I took this and made it O(n) as follows:
By subdividing the planar region into grid cells and imposing the restriction that each grid cell contains exactly one seed anywhere inside it, each seed is guaranteed to be no further apart than 2 grid cells diagonally. Therefore the inner loop above can be skipped for any seed more than this distance away from the seed S(i), resulting in about 8 intersection operations per seed. This is an O(n) algorithm, actually more like O(8n), and the execution time increases linearly as n increases, rather than exponentially.
I provided a demonstration, documentation, and code here: https://www.printables.com/model/831732 ~Anachronist (talk) 05:17, 19 April 2024 (UTC)
- See WP:NOR. We cannot include material here unless it has already been reliably published, and this talk page is only for discussions of article improvements, which for new material can only be based on published sources. But also, what do you do when the input sites are not evenly spaced and have no grid with exactly one point inside each grid cell? —David Eppstein (talk) 06:24, 19 April 2024 (UTC)
- I'm well aware of WP:NOR, you and I have been editing Wikipedia for about the same length of time, and my comment above does contain a suggestion for improving an article, if a name for the O(n2) algorithm can be found. The algorithm is so simple I would be surprised if no one has published it. I've done some cursory searching but haven't found it yet. I didn't create that O(n2) algorithm. I found it originally in a github project. All I did was impose a requirement on the input to cause the algorithm to be O(n), and I know that cannot be included here because as far as I know, that is my own original research. However, at my age, I've grown accustomed to learning that new ideas I get have already been thought of by someone else, so you never know.
- Your final question makes no sense. If you look at what I linked, you'll see the input sites (I assume you mean seeds) are never evenly spaced. What makes it O(n) is the requirement that each grid cell contains exactly one seed at any random position inside the cell. This still gives you a random distribution of seeds, but eliminates the need to test seeds farther than away from the seed for which a voronoi cell is being generated. If you don't put a seed in each cell, all bets are off; you get a pattern that may have errors because there may have been a seed farther away that needed testing. ~Anachronist (talk) 06:39, 19 April 2024 (UTC)
What makes it O(n) is the requirement that each grid cell contains exactly one seed at any random position inside the cell.
- An algorithm for constructing the Voronoi diagram needs to work with any arbitrary placement of the generating points, not just ones which round to a square grid. –jacobolus (t) 16:07, 19 April 2024 (UTC)
- That is absolutely false. An algorithm can certainly specify input conditions for it to work. Examples in mathematics abound.
- For example, the most basic fast fourier transform mandates that the input quantity be a power of two. A sine transform requires the bounds to be zero, a cosine transform requires the derivative at the bounds to be zero. Newton's method requires the starting point to not be near a local minimum in the function, and other requirements to prevent the solution from endlessly oscillating. An algorithm for solving sparse linear systems may require the input matrix to be tridiagonal, block diagonal, banded, or whatever. I could go on. The point is that many algorithms prohibit "arbitrary" inputs.
- In this case, an algorithm for generating an O(n) voronoi pattern requires an arrangement of seeds with one seed per grid cell, with each seed placed at an arbitrary random location in each cell.
- But that's all irrelevant. There's no way my idea for an O(n) algorithm is going to get into this article; I knew that already. I am instead asking the community if anyone is familiar with the O(n2) algorithm I described, which I initially found on GitHub, and whether anything like it has ever been published. ~Anachronist (talk) 00:12, 20 April 2024 (UTC)
- The idea of using a grid, and hoping that most grid cells have few points and few neighbors, is definitely not new. See:
- A. Maus. Delaunay triangulation and the convex hull of points in expected linear time. BIT 24:151-163, 1984. doi:10.1007/BF01937482. (It's Delaunay rather than Voronoi but they're the same thing.)
- Rex A. Dwyer. Higher-Dimensional Voronoi Diagrams in Linear Expected Time. Discret. Comput. Geom. 6: 343-367, 1991. doi:10.1007/BF02574694
- The difference is that the algorithms from these publications take arbitrary point sets as input, as a Voronoi diagram does, and then analyze their running time as linear for average-case inputs. They do not take the parameters of a grid as input, generate an input from that grid, and only work for inputs that are generated in this way, as yours appears to do.
- As for the idea that each Voronoi cell can be generated by intersecting halfspaces, one for each other site: this is also standard, and presented in many sources as a description of the Voronoi cells. It is not commonly presented as an algorithm for constructing the whole diagram because it is not very efficient and what's the point of presenting slow algorithms instead of fast ones? And unless you are doing something complicated, your time analysis is incorrect: in 2d and 3d it takes time to construct the intersection of halfspaces and therefore the overall algorithm takes time .
- —David Eppstein (talk) 01:34, 20 April 2024 (UTC)
- Thank you. That first source got the idea: "The expected execution time is achieved when the data are (not too far from) uniformly distributed" — which is the case I proposed, the difference being that there is guaranteed to be one seed in every grid cell, and even though the seeds can be very close together, they can be no farther apart than the farthest corners of two adjacent diagonal cells.
- As far as I've been able to determine by measuring execution times of my algorithm, it's linear. Each seed requires an intersection of 8 half planes, less at the edges of the data set. The execution time of an intersection between two things (a half plane and the result of the previous intersections) is fairly constant. The algorithm doesn't perform an intersection of all 8 half planes at once, but even if it did, the execution time scales linearly with the number of seeds.
- You ask, "what's the point of presenting slow algorithms instead of fast ones?" My answer: (a) the article already names the Bowyer–Watson algorithm, which can be O(n2), and (b) the one I describe above is simple for a layperson to understand. Wikipedia article should be accessible by a broad audience. ~Anachronist (talk) 02:02, 20 April 2024 (UTC)
- Wikipedia articles should reflect published material found in reliable sources, not the partial results of tentative experiments performed by Wikipedians. –jacobolus (t) 08:17, 20 April 2024 (UTC)
- I agree with that first part of that statement, but you are quite wrong on the second part: my results are not partial and my experiements were not tentative. ~Anachronist (talk) 00:25, 22 April 2024 (UTC)
- Sorry, that was unnecessary on my part. I don't know the details of what experiments you did, nor was it really relevant to my point. –jacobolus (t) 06:32, 22 April 2024 (UTC)
- I agree with that first part of that statement, but you are quite wrong on the second part: my results are not partial and my experiements were not tentative. ~Anachronist (talk) 00:25, 22 April 2024 (UTC)
- Wikipedia articles should reflect published material found in reliable sources, not the partial results of tentative experiments performed by Wikipedians. –jacobolus (t) 08:17, 20 April 2024 (UTC)
That is absolutely false. An algorithm can certainly specify input conditions
– It's not "absolutely false"; I just didn't express my point clearly enough so it didn't get through. For the context of Wikipedia, those input conditions should be broadly relevant to the subject as it appears in reliable sources. If there's a set of non-arbitrary inputs used broadly in the research literature, it's fine enough to mention it in a new section (whose title could be "Faster algorithms for special cases" or the like). Making up new restrictive cases with no previously applied theoretical or practical uses is fine for a new blog post (or research paper), but is entirely inappropriate for a Wikipedia article. –jacobolus (t) 08:25, 20 April 2024 (UTC)- Good idea. I hadn't considered writing about this in a blog post, but maybe I should. I haven't contributed to my blog in quite a while. ~Anachronist (talk) 00:25, 22 April 2024 (UTC)
- The idea of using a grid, and hoping that most grid cells have few points and few neighbors, is definitely not new. See:
Start a discussion about improving the Voronoi diagram page
Talk pages are where people discuss how to make content on Wikipedia the best that it can be. You can use this page to start a discussion with others about how to improve the "Voronoi diagram" page.