1572:, you and I have been editing Knowledge 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(n) 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(n) 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.
674:
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.
84:
74:
53:
1950:– It's not "absolutely false"; I just didn't express my point clearly enough so it didn't get through. For the context of Knowledge, 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
22:
611:. 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. --
1554:. 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? —
690:
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:
1871:
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)
1660:
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
538:
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
1867:
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
1766:
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
1742:
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
1507:
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
1097:
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
561:
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
316:
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
1575:
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
789:
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
689:
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
599:
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
1518:
This algorithm results in voronoi polygons around each seed. It's an O(n) 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
1332:
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.
673:
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
810:
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
1525:
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
1418:
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
254:
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
1221:
The first paragraph feels kind of dense to me and I was about to edit it, but being new to the editor side of Knowledge, 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
356:
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.
1312:
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.
349:
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?
1667:
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(n) algorithm I described, which I initially found
834:
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.
523:
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.
1611:
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.
1526:
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.
489:
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
205:
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.
606:
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
404:
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
232:(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
830:
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)
1609:
1664:
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.
1278:
258:
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 ...
140:
975:
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.
1954:
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 Knowledge article. –
1056:, 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
1872:
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.
1848:
811:
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.
217:. 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.
1803:
754:
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
1633:
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. –
503:
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.
1764:
1709:
1911:
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. ~
655:
1899:
Knowledge articles should reflect published material found in reliable sources, not the partial results of tentative experiments performed by Wikipedians. –
2007:
130:
858:. Google only gave me references to programs that do it. There should be a section on it, including the difference between Multiplicative and Additive.
626:
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
1512:
intersection operation with this half-plane and all previous half-planes generated in this loop end inner loop end outer loop
1883:
be O(n), and (b) the one I describe above is simple for a layperson to understand. Knowledge article should be accessible by a broad audience. ~
106:
2002:
1168:. 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.
1202:
1195:
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.
694:
612:
1966:
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. ~
434:
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.--
1927:
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. –
1237:
600:
than X space, which is too much!" since big-oh is basically a <= or < type inequality, depending on case, whereas omega is : -->
421:
333:
1282:
1487:
This would then simplify much of the later presentation which repeatedly adds "in the Euclidean plane" or the like as a qualifier. –
1169:
272:
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))?
97:
58:
373:
1475:. The concept of a Voronoi diagram has been generalized to use objects other than points as the seeds and to settings of higher
386:
251:
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 ...
1645:
That is absolutely false. An algorithm can certainly specify input conditions for it to work. Examples in mathematics abound.
1160:
Interesting maps appeared on Reddits /r/mapporn including two real life maps of the US and world as a Voronoi diagram. They
1629:
What makes it O(n) is the requirement that each grid cell contains exactly one seed at any random position inside the cell.
353:
Also, it would be interesting to know what "human algorithms" were used to draw 2D voronoi diagrams back before computers.
1371:
In general, a cross section of a 3D Voronoi tessellation is not a 2D Voronoi tessellation itself, since the cells are all
1009:." Delete points one-at-a-time and draw separate Voronoi diagrams? And this tesselates space? This doesn't make sense.
1688:
The idea of using a grid, and hoping that most grid cells have few points and few neighbors, is definitely not new. See:
1579:
710:
33:
1509:
1103:
174:
Correct --- and that article is even stubbier than this one. Maybe I'll work on both of them further at some point.
1767:
of fast ones? And unless you are doing something complicated, your time analysis is incorrect: in 2d and 3d it takes
840:
790:
from the finite case? Is it the set of points in the space, or the set of cells associated with each point in S?
215:
773:
Actually, S just needs to include all it's limit points. Including 0 in your example fixes it with no problems.
1858:
1559:
1297:
855:
698:
679:
616:
1206:
1099:
1083:
1069:
1014:
417:
329:
1875:
You ask, "what's the point of presenting slow algorithms instead of fast ones?" My answer: (a) the article
1173:
836:
1649:
1472:
1233:
1146:
816:
576:
163:
664:
508:
389:. Not sure how (or whether) to include it in the page though. The applications is already a bit messy...
192:
1972:
1917:
1889:
1678:
1618:
1539:
1468:
986:
of points and I draw their Voronoi diagram. I presume that's the "1st-order" Voronoi diagram. We have
394:
237:
207:
39:
1383:
Both parts of this statement are clearly true, but the applicability of "since" is not obvious to me. —
413:
325:
83:
562:
I'd recommend the Qhull program (see links) which works by computing a convex hull in n-dimensions. --
233:
1656:
requires the bounds to be zero, a cosine transform requires the derivative at the bounds to be zero.
1456:
1225:
1198:
584:
567:
491:
479:
455:
439:
409:
369:
365:
361:
321:
21:
1958:
1931:
1903:
1854:
1808:
1637:
1555:
1491:
1348:
1314:
1293:
990:= 2. So I am told to "start with the 1st-order Voronoi diagram and replace each cell generated by
874:
763:
675:
525:
167:
105:
on Knowledge. If you would like to participate, please visit the project page, where you can join
1464:
1432:
1403:
1352:
1338:
1329:
1318:
1079:
1065:
1010:
175:
89:
1868:
together, they can be no farther apart than the farthest corners of two adjacent diagonal cells.
1805:
time to construct the intersection of halfspaces and therefore the overall algorithm takes time
73:
52:
1770:
385:
I did a quick Google search for this. I couldn't find a national-level example, but I did find
306:
1669:
1388:
1229:
1142:
1132:
812:
188:
1048:". That is utterly unclear: it requires us to measure the distance from a point to a set of
1967:
1912:
1884:
1731:
1716:
1673:
1657:
1613:
1534:
1440:
1191:
has apparently shut down due to a price increase on the Google Maps API, and the version on
898:
Although normal Voronoi cells are defined as the set of points closest to a single point in
863:
795:
778:
390:
1414:
fundamental definition should be points in the Euclidean plane, not arbitrary metric spaces
1436:
1262:
735:
580:
563:
475:
451:
435:
292:
1504:
One really simple O(n) algorithm isn't described in this article. Here's the pseudocode:
1274:
But what does it mean for two points of the set to be "adjacent on the convex hull" ???
305:"Spatial Query Processing Utilizing Voronoi Diagrams" from the Google TechTalks series:
1955:
1928:
1900:
1653:
1634:
1488:
1025:
759:
751:
727:
660:
504:
218:
1749:
1694:
1419:
section about generalizations. Let me recommend a first paragraph along the lines of:
1265:
and a discrete set of points is given. Then two points of the set are adjacent on the
1996:
1569:
1551:
1399:
1334:
711:
http://cstheory.stackexchange.com/questions/17331/outer-part-of-voronoi-diagram-in-3d
552:
495:
431:
1515:
Does anyone know if this algorithm has a name that can be mentioned in the article?
629:
1480:
1384:
1128:
691:
471:
236:(his CIC report), or to the page you mentioned above, should go in the References?
1370:
1064:
in mid-sentence should warn us that whoever typed this wasn't paying attention.)
1424:
1266:
859:
791:
774:
755:
102:
608:
1375:
1372:
1277:
I hope someone knowledgeable about this subject can clarify this for readers.
982:
Next, suppose I want to generate the 2nd-order Voronoi diagram. I have a set
277:
259:
79:
1948:
That is absolutely false. An algorithm can certainly specify input conditions
1127:
I downloaded this but see no content other than a caption. How about you? —
919:
Higher-order Voronoi diagrams can be generated recursively. To generate the
713:
in the solutions two point sets are described which require Omega(n^2) in 3D.
659:, or for "large d" (for d=3 it is not so bad, for non-gigantic point sets).
539:
what happens if this algorithm creates segments without a point inside them?
1476:
1467:) to that seed than to any other. The Voronoi diagram of a set of points is
1121:
1726:
Rex A. Dwyer. Higher-Dimensional Voronoi Diagrams in Linear Expected Time.
1576:
distribution of seeds, but eliminates the need to test seeds farther than
1530:
1292:
What do you think it means for two vertices of a polygon to be adjacent? —
723:
540:
450:
I've simplified the lead section which should make it a little simpler.--
1977:
1961:
1934:
1922:
1906:
1894:
1862:
1746:
As for the idea that each Voronoi cell can be generated by intersecting
1683:
1640:
1623:
1563:
1544:
1494:
1407:
1392:
1356:
1342:
1322:
1301:
1286:
1241:
1210:
1177:
1150:
1136:
1107:
1087:
1073:
1018:
878:
867:
844:
820:
799:
782:
767:
722:
In the Definition section of the other article it claims that "For any (
702:
683:
668:
620:
588:
571:
555:
528:
512:
498:
483:
459:
443:
398:
377:
337:
295:
280:
262:
195:
1735:
1720:
1347:
Great, thanks for checking out the edit, and thanks for your feedback.
317:
order-k diagrams and the complexity of generating an order-k diagram.
1248:
What are "adjacent" points on a convex hull? Clarification is needed
276:
If you can describe such algoritms accurately, then please add them.
255:
diffusion processes, etc. How about other definitions of "center"?
1188:
234:
http://www.epi.msu.edu/johnsnow/Snow%20pub%20doc/CIC-JSRpt_SF12.htm
1723:. (It's Delaunay rather than Voronoi but they're the same thing.)
1269:
if and only if their Voronoi cells share an infinitely long side.
1165:
1161:
906:-order Voronoi cells are defined as the set of points closest to
1743:
inputs that are generated in this way, as yours appears to do.
15:
1508:
need be no bigger than the span of seeds. Perform a
1328:
I have a few concerns besides COI about your proposed edit.
307:
http://video.google.com/videoplay?docid=-2755539754474649930
1463:, consisting of all points of the plane closer (at smaller
1661:
point is that many algorithms prohibit "arbitrary" inputs.
1529:
I provided a demonstration, documentation, and code here:
579:(the dual problem) has some more details of algorithms. --
1672:, and whether anything like it has ever been published. ~
595:
Space complexity mentioned in the Generalizations section
1032:
th-order Voronoi cell if they both have the same set of
301:
Additional Material to Consider for Uses and Application
1691:
A. Maus. Delaunay triangulation and the convex hull of
1652:
mandates that the input quantity be a power of two. A
1192:
931:− 1)-order diagram and replace each cell generated by
914:. Higher-order Voronoi diagrams also subdivide space.
228:
Aha. The Voronoi line wasn't present in Snow's map in
1811:
1773:
1752:
1697:
1582:
1308:
Information about the surface area of cells relevant?
634:
1604:{\displaystyle 2{\sqrt {2}}\times {\text{gridsize}}}
1439:
into regions close to each of a given finite set of
101:, a collaborative effort to improve the coverage of
1040:. That is clear. The text above says "closest to
1842:
1797:
1758:
1703:
1603:
1078:...the second paragraph is still unclear at best.
647:
750:". This is untrue as shown by the example in the
1398:I agree. Edited to remove that clause entirely.
692:http://www.pi6.fernuni-hagen.de/publ/tr277.pdf--
1001:} with a Voronoi diagram generated on the set
959:} with a Voronoi diagram generated on the set
470:If you have just three points do you get the
8:
826:Conflict between Introduction and Definition
609:http://www.math.tau.ac.il/~michas/wads95.pdf
291:Voronoi appears to be of Ukranian descent.--
1455:). For each seed there is a corresponding
1223:
1217:Suggestion to simplify the first paragraph
1196:
47:
1879:names the Bowyer–Watson algorithm, which
1822:
1810:
1772:
1751:
1696:
1596:
1586:
1581:
1522:I took this and made it O(n) as follows:
633:
1531:https://www.printables.com/model/831732
1483:with an alternative notion of distance.
1098:this link soon unless someone objects.
230:On the mode of communication of cholera
49:
19:
1947:
1628:
1028:. It says two points are in the same
1279:2601:200:C000:1A0:F447:6226:63A4:B204
7:
387:an example for the states of the USA
95:This article is within the scope of
1183:Dead link to Melbourne school zones
38:It is of interest to the following
1519:corresponds to a voronoi polygon.
14:
2008:Mid-priority mathematics articles
115:Knowledge:WikiProject Mathematics
1711:points in expected linear time.
923:-order Voronoi diagram from set
118:Template:WikiProject Mathematics
82:
72:
51:
20:
1500:I made a O(n) voronoi algorithm
1479:or more generally to arbitrary
854:I'm looking for information on
158:Dual to Delaunay triangulation?
135:This article has been rated as
1843:{\displaystyle O(n^{2}\log n)}
1837:
1815:
1792:
1777:
1108:01:23, 11 September 2010 (UTC)
845:07:20, 30 September 2011 (UTC)
499:06:24, 25 September 2007 (UTC)
484:22:22, 24 September 2007 (UTC)
196:15:30, 15 September 2006 (UTC)
1:
1495:20:10, 3 September 2023 (UTC)
1357:10:29, 29 December 2022 (UTC)
1343:17:45, 28 December 2022 (UTC)
1323:15:41, 28 December 2022 (UTC)
1122:A Voronoi diagram on a sphere
888:Higher-order Voronoi diagrams
768:02:28, 12 February 2009 (UTC)
669:16:45, 10 December 2007 (UTC)
513:16:39, 10 December 2007 (UTC)
281:16:07, 23 November 2005 (UTC)
109:and see a list of open tasks.
2003:C-Class mathematics articles
1648:For example, the most basic
1211:10:45, 27 January 2020 (UTC)
460:09:45, 29 October 2012 (UTC)
444:09:28, 29 October 2012 (UTC)
430:I've removed the incomplete
1510:constructive solid geometry
1408:13:34, 25 August 2023 (UTC)
1393:03:07, 25 August 2023 (UTC)
1088:11:59, 11 August 2009 (UTC)
1074:11:58, 11 August 2009 (UTC)
1019:11:45, 11 August 2009 (UTC)
589:16:11, 8 October 2007 (UTC)
572:15:40, 8 October 2007 (UTC)
556:13:47, 8 October 2007 (UTC)
529:17:43, 1 October 2007 (UTC)
399:10:23, 22 August 2011 (UTC)
378:15:45, 13 August 2010 (UTC)
338:19:45, 1 October 2008 (UTC)
247:Artwork; unusual statements
200:
2024:
1978:00:25, 22 April 2024 (UTC)
1962:08:25, 20 April 2024 (UTC)
1935:06:32, 22 April 2024 (UTC)
1923:00:25, 22 April 2024 (UTC)
1907:08:17, 20 April 2024 (UTC)
1895:02:02, 20 April 2024 (UTC)
1863:01:34, 20 April 2024 (UTC)
1798:{\displaystyle O(n\log n)}
1684:00:12, 20 April 2024 (UTC)
1641:16:07, 19 April 2024 (UTC)
1624:06:39, 19 April 2024 (UTC)
1564:06:24, 19 April 2024 (UTC)
1545:05:17, 19 April 2024 (UTC)
1261:Assume the setting is the
873:Here you are. - Altenmann
684:12:45, 16 March 2009 (UTC)
312:Order of a Voronoi diagram
1137:01:47, 12 July 2012 (UTC)
879:18:59, 26 June 2009 (UTC)
868:00:41, 25 June 2009 (UTC)
850:Weighted Voronoi Diagrams
821:10:33, 5 March 2009 (UTC)
800:03:54, 25 June 2009 (UTC)
783:03:03, 25 June 2009 (UTC)
738:and for almost any point
263:20:28, 26 July 2005 (UTC)
221:07:48, Apr 11, 2005 (UTC)
210:00:24, 2005 Apr 10 (UTC)
134:
67:
46:
1302:19:31, 11 May 2022 (UTC)
1287:19:16, 11 May 2022 (UTC)
1189:melbourneschoolzones.com
1178:15:37, 3 July 2013 (UTC)
1151:01:53, 4 July 2021 (UTC)
856:weighted Voronoi diagram
806:Question about existence
742:, there is one point of
703:15:50, 9 July 2013 (UTC)
621:16:05, 9 July 2013 (UTC)
296:08:45, 1 June 2006 (UTC)
240:09:12, 2005 Apr 11 (UTC)
170:10:37 Feb 2, 2003 (UTC)
141:project's priority scale
1256:contains this passage:
1242:07:07, 5 May 2020 (UTC)
718:Discrete set of points?
201:John Snow's cholera map
191:in materials science.--
187:Another Example is the
178:22:28 Feb 5, 2003 (UTC)
98:WikiProject Mathematics
1844:
1799:
1760:
1728:Discret. Comput. Geom.
1705:
1650:fast fourier transform
1605:
1473:Delaunay triangulation
651:
577:Delaunay triangulation
164:delaunay triangulation
28:This article is rated
1845:
1800:
1761:
1706:
1606:
1036:nearest neighbors in
652:
648:{\displaystyle d: -->
1809:
1771:
1750:
1695:
1580:
632:
492:equilateral triangle
162:This is the dual to
121:mathematics articles
1141:Blank for me too.
1117:New external link:
1093:Recently Added Link
892:This article says:
756:accumulation points
214:See Figure 12.6 at
1840:
1795:
1756:
1736:10.1007/BF02574694
1730:6: 343-367, 1991.
1721:10.1007/BF01937482
1715:24:151-163, 1984.
1701:
1601:
1568:I'm well aware of
927:, start with the (
645:
424:) 29 October 2012
90:Mathematics portal
34:content assessment
1976:
1921:
1893:
1759:{\displaystyle n}
1704:{\displaystyle n}
1682:
1622:
1599:
1591:
1543:
1244:
1228:comment added by
1213:
1201:comment added by
1156:real life voronoi
1100:RuppertsAlgorithm
426:
412:comment added by
381:
364:comment added by
341:
324:comment added by
189:Wigner-Seitz cell
183:Wigner-Seitz cell
155:
154:
151:
150:
147:
146:
2015:
1970:
1915:
1887:
1849:
1847:
1846:
1841:
1827:
1826:
1804:
1802:
1801:
1796:
1765:
1763:
1762:
1757:
1710:
1708:
1707:
1702:
1676:
1616:
1610:
1608:
1607:
1602:
1600:
1597:
1592:
1587:
1537:
1379:
837:RedBlackTreeNode
658:
654:
653:
646:
549:
546:
543:
425:
406:
380:
358:
340:
318:
238:Gareth McCaughan
208:Gareth McCaughan
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
2023:
2022:
2018:
2017:
2016:
2014:
2013:
2012:
1993:
1992:
1818:
1807:
1806:
1769:
1768:
1748:
1747:
1693:
1692:
1658:Newton's method
1578:
1577:
1513:
1502:
1437:Euclidean plane
1429:Voronoi diagram
1416:
1367:
1310:
1263:Euclidean plane
1250:
1219:
1185:
1158:
1143:// NomadicVoxel
1115:
1095:
1000:
958:
948:
941:
890:
852:
828:
808:
758:" is required.
736:Euclidean space
720:
628:
627:
597:
547:
544:
541:
536:
521:
468:
407:
359:
347:
319:
314:
303:
289:
270:
249:
203:
185:
160:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
2021:
2019:
2011:
2010:
2005:
1995:
1994:
1991:
1990:
1989:
1988:
1987:
1986:
1985:
1984:
1983:
1982:
1981:
1980:
1945:
1944:
1943:
1942:
1941:
1940:
1939:
1938:
1937:
1873:
1869:
1855:David Eppstein
1851:
1839:
1836:
1833:
1830:
1825:
1821:
1817:
1814:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1755:
1744:
1740:
1739:
1738:
1724:
1700:
1665:
1662:
1654:sine transform
1646:
1631:
1595:
1590:
1585:
1573:
1556:David Eppstein
1506:
1501:
1498:
1485:
1484:
1471:to that set's
1415:
1412:
1411:
1410:
1381:
1380:
1366:
1363:
1362:
1361:
1360:
1359:
1309:
1306:
1305:
1304:
1294:David Eppstein
1249:
1246:
1218:
1215:
1203:129.194.48.105
1184:
1181:
1157:
1154:
1125:
1124:
1114:
1111:
1094:
1091:
1060:to lower-case
1022:
998:
980:
979:
973:
972:
970:
969:
968:
953:
946:
939:
917:
915:
889:
886:
884:
882:
881:
851:
848:
827:
824:
807:
804:
803:
802:
786:
785:
752:Discrete space
719:
716:
715:
714:
706:
705:
695:128.119.40.196
676:Enisbayramoglu
644:
641:
637:
624:
623:
613:128.119.40.196
596:
593:
592:
591:
574:
535:
532:
526:Dylan Thurston
520:
517:
516:
515:
501:
467:
464:
463:
462:
447:
446:
402:
401:
346:
343:
313:
310:
302:
299:
288:
287:pronunciation?
285:
284:
283:
269:
266:
248:
245:
244:
243:
242:
241:
223:
222:
202:
199:
193:149.220.16.110
184:
181:
180:
179:
168:Chas zzz brown
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
2020:
2009:
2006:
2004:
2001:
2000:
1998:
1979:
1974:
1969:
1965:
1964:
1963:
1960:
1957:
1953:
1949:
1946:
1936:
1933:
1930:
1926:
1925:
1924:
1919:
1914:
1910:
1909:
1908:
1905:
1902:
1898:
1897:
1896:
1891:
1886:
1882:
1878:
1874:
1870:
1866:
1865:
1864:
1860:
1856:
1852:
1834:
1831:
1828:
1823:
1819:
1812:
1789:
1786:
1783:
1780:
1774:
1753:
1745:
1741:
1737:
1733:
1729:
1725:
1722:
1718:
1714:
1698:
1690:
1689:
1687:
1686:
1685:
1680:
1675:
1671:
1666:
1663:
1659:
1655:
1651:
1647:
1644:
1643:
1642:
1639:
1636:
1632:
1630:
1627:
1626:
1625:
1620:
1615:
1593:
1588:
1583:
1574:
1571:
1567:
1566:
1565:
1561:
1557:
1553:
1549:
1548:
1547:
1546:
1541:
1536:
1532:
1527:
1523:
1520:
1516:
1511:
1505:
1499:
1497:
1496:
1493:
1490:
1482:
1481:metric spaces
1478:
1474:
1470:
1466:
1462:
1458:
1454:
1450:
1446:
1442:
1438:
1434:
1430:
1426:
1422:
1421:
1420:
1413:
1409:
1405:
1401:
1397:
1396:
1395:
1394:
1390:
1386:
1377:
1374:
1369:
1368:
1364:
1358:
1354:
1350:
1346:
1345:
1344:
1340:
1336:
1331:
1327:
1326:
1325:
1324:
1320:
1316:
1307:
1303:
1299:
1295:
1291:
1290:
1289:
1288:
1284:
1280:
1275:
1272:
1270:
1268:
1264:
1257:
1255:
1247:
1245:
1243:
1239:
1235:
1231:
1227:
1216:
1214:
1212:
1208:
1204:
1200:
1194:
1190:
1182:
1180:
1179:
1175:
1171:
1167:
1163:
1155:
1153:
1152:
1148:
1144:
1139:
1138:
1134:
1130:
1123:
1120:
1119:
1118:
1112:
1110:
1109:
1105:
1101:
1092:
1090:
1089:
1085:
1081:
1080:Michael Hardy
1076:
1075:
1071:
1067:
1066:Michael Hardy
1063:
1059:
1055:
1051:
1047:
1043:
1039:
1035:
1031:
1027:
1026:this web page
1021:
1020:
1016:
1012:
1011:Michael Hardy
1008:
1004:
997:
993:
989:
985:
978:
977:
976:
971:
966:
962:
956:
952:
945:
938:
934:
930:
926:
922:
918:
916:
913:
909:
905:
901:
897:
896:
895:
894:
893:
887:
885:
880:
877:
872:
871:
870:
869:
865:
861:
857:
849:
847:
846:
842:
838:
832:
825:
823:
822:
818:
814:
805:
801:
797:
793:
788:
787:
784:
780:
776:
772:
771:
770:
769:
765:
761:
757:
753:
749:
745:
741:
737:
734:of points in
733:
729:
725:
724:topologically
717:
712:
708:
707:
704:
700:
696:
693:
688:
687:
686:
685:
681:
677:
671:
670:
666:
662:
642:
638:
635:
622:
618:
614:
610:
605:
604:
603:
594:
590:
586:
582:
578:
575:
573:
569:
565:
560:
559:
558:
557:
554:
550:
533:
531:
530:
527:
518:
514:
510:
506:
502:
500:
497:
493:
488:
487:
486:
485:
481:
477:
473:
465:
461:
457:
453:
449:
448:
445:
441:
437:
433:
429:
428:
427:
423:
419:
415:
411:
400:
396:
392:
388:
384:
383:
382:
379:
375:
371:
367:
363:
354:
351:
344:
342:
339:
335:
331:
327:
323:
311:
309:
308:
300:
298:
297:
294:
286:
282:
279:
275:
274:
273:
267:
265:
264:
261:
256:
252:
246:
239:
235:
231:
227:
226:
225:
224:
220:
216:
213:
212:
211:
209:
198:
197:
194:
190:
182:
177:
176:Michael Hardy
173:
172:
171:
169:
165:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
1951:
1880:
1876:
1727:
1712:
1528:
1524:
1521:
1517:
1514:
1503:
1486:
1461:Voronoi cell
1460:
1452:
1448:
1444:
1428:
1417:
1382:
1311:
1276:
1273:
1260:
1258:
1253:
1252:The section
1251:
1230:NomadicVoxel
1224:— Preceding
1222:location."
1220:
1197:— Preceding
1186:
1159:
1140:
1126:
1116:
1113:WorldMap.pdf
1096:
1077:
1061:
1057:
1053:
1049:
1045:
1041:
1037:
1033:
1029:
1024:OK, I found
1023:
1006:
1002:
995:
991:
987:
983:
981:
974:
964:
960:
954:
950:
943:
936:
932:
928:
924:
920:
911:
907:
903:
899:
891:
883:
853:
833:
829:
813:Omar.zanusso
809:
747:
743:
739:
731:
721:
672:
625:
598:
537:
522:
472:Fermat point
469:
466:Fermat point
414:82.249.88.27
408:— Preceding
403:
355:
352:
348:
326:Sunupsundown
315:
304:
290:
271:
257:
253:
250:
229:
204:
186:
166:, isn't it?
161:
137:Mid-priority
136:
96:
62:Mid‑priority
40:WikiProjects
1968:Anachronist
1913:Anachronist
1885:Anachronist
1674:Anachronist
1614:Anachronist
1535:Anachronist
1459:, called a
1425:mathematics
1330:WP:PREPRINT
1267:convex hull
1193:archive.org
1170:92.23.66.70
746:closest to
391:Warrickball
360:—Preceding
320:—Preceding
268:Algorithms?
112:Mathematics
103:mathematics
59:Mathematics
1997:Categories
1453:generators
1254:Properties
1052:points in
1044:points in
910:points in
657:2}" /: -->
581:Salix alba
564:Salix alba
534:Algorithm?
476:Salix alba
366:Bobbyleeds
345:Non mathy?
293:MinorEdits
1956:jacobolus
1929:jacobolus
1901:jacobolus
1670:on GitHub
1635:jacobolus
1489:jacobolus
1477:dimension
1433:partition
1376:polyhedra
1187:The site
760:TomC phys
661:PhiloMath
505:PhiloMath
405:deletion.
219:Gandalf61
1598:gridsize
1465:distance
1443:(called
1400:Eigenbra
1349:Ryancots
1335:Eigenbra
1315:Ryancots
1238:contribs
1226:unsigned
1199:unsigned
728:discrete
631:2}": -->
601:or : -->
519:Software
422:contribs
410:unsigned
374:contribs
362:unsigned
334:contribs
322:unsigned
1877:already
1435:of the
1385:Tamfang
1365:section
1129:Tamfang
949:, ...,
139:on the
30:C-class
1570:WP:NOR
1552:WP:NOR
1457:region
1441:points
1373:convex
860:Nekura
792:Nekura
775:Nekura
709:Here:
432:WP:AFD
36:scale.
1451:, or
1449:sites
1445:seeds
1431:is a
875:: -->
656:: -->
649:: -->
640:: -->
639:: -->
630:: -->
496:Míkka
452:Salix
436:Salix
278:linas
260:linas
1973:talk
1918:talk
1890:talk
1859:talk
1679:talk
1619:talk
1560:talk
1550:See
1540:talk
1469:dual
1427:, a
1404:talk
1389:talk
1353:talk
1339:talk
1319:talk
1298:talk
1283:talk
1234:talk
1207:talk
1174:talk
1166:here
1164:and
1162:here
1147:talk
1133:talk
1104:talk
1084:talk
1070:talk
1015:talk
864:talk
841:talk
817:talk
796:talk
779:talk
764:talk
730:set
699:talk
680:talk
665:talk
617:talk
585:talk
568:talk
553:Talk
509:talk
480:talk
474:? --
456:talk
440:talk
418:talk
395:talk
370:talk
330:talk
1959:(t)
1952:new
1932:(t)
1904:(t)
1881:can
1829:log
1784:log
1732:doi
1717:doi
1713:BIT
1638:(t)
1492:(t)
1423:In
994:= {
935:= {
602:=.
494:.`'
458:):
442:):
131:Mid
1999::
1861:)
1832:
1787:
1594:×
1562:)
1447:,
1406:)
1391:)
1355:)
1341:)
1321:)
1300:)
1285:)
1271:"
1240:)
1236:•
1209:)
1176:)
1149:)
1135:)
1106:)
1086:)
1072:)
1017:)
1005:−
963:−
957:−1
942:,
902:,
866:)
843:)
835:--
819:)
798:)
781:)
766:)
726:)
701:)
682:)
667:)
650:2}
619:)
587:)
570:)
551:|
524:--
511:)
482:)
420:•
397:)
376:)
372:•
336:)
332:•
1975:)
1971:(
1920:)
1916:(
1892:)
1888:(
1857:(
1853:—
1850:.
1838:)
1835:n
1824:2
1820:n
1816:(
1813:O
1793:)
1790:n
1781:n
1778:(
1775:O
1754:n
1734::
1719::
1699:n
1681:)
1677:(
1621:)
1617:(
1612:~
1589:2
1584:2
1558:(
1542:)
1538:(
1533:~
1402:(
1387:(
1378:.
1351:(
1337:(
1317:(
1296:(
1281:(
1259:"
1232:(
1205:(
1172:(
1145:(
1131:(
1102:(
1082:(
1068:(
1062:n
1058:N
1054:S
1050:n
1046:S
1042:n
1038:S
1034:n
1030:n
1013:(
1007:X
1003:S
999:1
996:x
992:X
988:n
984:S
967:.
965:X
961:S
955:n
951:x
947:2
944:x
940:1
937:x
933:X
929:n
925:S
921:n
912:S
908:n
904:N
900:S
876:t
862:(
839:(
815:(
794:(
777:(
762:(
748:x
744:S
740:x
732:S
697:(
678:(
663:(
643:2
636:d
615:(
583:(
566:(
548:P
545:I
542:J
507:(
478:(
454:(
438:(
416:(
393:(
368:(
328:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
