tag:blogger.com,1999:blog-8890204.post4351491398538623799..comments2014-03-31T08:13:43.617-04:00Comments on My Biased Coin: Any Good Voronoi Code Out There?Michael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-8890204.post-5982833607895049552013-01-22T06:32:17.935-05:002013-01-22T06:32:17.935-05:00This might be useful!! nice way of visualizing an ...This might be useful!! nice way of visualizing an insertion.. a deletion is highly probably as easy!<br /><br />http://bl.ocks.org/4060366Amjad M Daoudhttp://ijj.acm.org/editor.htmnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-37934831307003237392013-01-19T16:32:10.172-05:002013-01-19T16:32:10.172-05:00In my experience, MATLAB is the path of least resi...In my experience, MATLAB is the path of least resistance for quickly (inefficiently) testing out ideas. Apparently there are ways to add/delete points without rebuilding everything but when I did these kinds of tests, I just rebuilt everytime since I was going to implement things correctly later and I am not sure how much functionality octave supports.<br /><br />http://www.mathworks.com/products/matlab/examples.html?file=/products/demos/shipping/matlab/demoDelaunayTri.html#13<br /><br /><br />CGAL has a structure for performing dynamic insertion/deletion that is fast most of the time. But just getting started with CGAL takes some effort...<br /><br />http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_37.10<br /><br />About reflecting points: can't you compute the Voronoi diagram and then only reflect points with Voronoi cells that touch the boundary and add them to the triangulation. If you are already writing/finding the code to clip Voronoi cells to the boundary (and incrementally adding points), that should be not too bad. And "usually" you only have to reflect O(n^{1/2}) points (in 2D).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-62893917186568636602013-01-10T07:34:50.874-05:002013-01-10T07:34:50.874-05:00Jeff --
Both your comments are good/useful in th...Jeff -- <br /><br />Both your comments are good/useful in theory. In practice, however, making 9 copies of the points is going to be a 10x slowdown; always nice to avoid that if possible (if there's an easy way to do so). Similarly, just because the two are duals doesn't mean that one isn't easier to work with than another. (Or, in particular, the point is I don't want to "work with" either; I just want something that gives me areas of Voronoi cells out of the box.) Michael Mitzenmacherhttp://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-64248249595016248392013-01-10T02:05:55.835-05:002013-01-10T02:05:55.835-05:00I was wondering if Delaunay triangulations might p...I was wondering if Delaunay triangulations might prove easier to deal with<br /><br />Nope. Any data structure that represents a Voronoi diagram can be interpreted as a data structure that represents a Delaunay triangulation and vice versa. Thus, any algorithm that computes Voronoi diagrams also computes Delaunay triangulations and vice versa. Duality is your friend.<br />Jeff Ericksonhttp://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-82896707592032435712013-01-10T02:05:06.349-05:002013-01-10T02:05:06.349-05:00This comment has been removed by the author.Jeff Ericksonhttp://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-83789574525816349652013-01-10T02:03:21.671-05:002013-01-10T02:03:21.671-05:00To compute Voronoi diagrams on the torus, build a ...To compute Voronoi diagrams on the torus, build a 3x3 grid of squares, dump a copy of your point set in each square, compute the Voronoi diagram of the 9n points, and then clip to the center square.Jeff Ericksonhttp://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-62519236882315216012013-01-09T22:30:51.340-05:002013-01-09T22:30:51.340-05:00Someone created a dynamic voroni in d3.js. You can...Someone created a dynamic voroni in d3.js. You can add, remove, and drag nodes around the screen: http://bl.ocks.org/1734663Ricardonoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-83243301672807477062013-01-09T14:35:39.979-05:002013-01-09T14:35:39.979-05:00To add to that: computing the area of a voronoi r...To add to that: computing the area of a voronoi region is a primitive in "Natural Neighbor" interpolation. The code for that is given here:<br /><br />http://code.google.com/p/nn-c/OINKYnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-51498140634391448972013-01-09T14:23:10.127-05:002013-01-09T14:23:10.127-05:00Thanks -- I was wondering if Delaunay triangulatio...Thanks -- I was wondering if Delaunay triangulations might prove easier to deal with, but wasn't clear on how hard getting cell areas and things might be. I'll take a look. Michael Mitzenmacherhttp://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-42788792913193331462013-01-09T14:16:52.729-05:002013-01-09T14:16:52.729-05:00Yep. Try any reasonable implementation of Delaunay...Yep. Try any reasonable implementation of Delaunay triangulation. Any such implementation would have insertions and deletions. CGAL is a good starting point. I would just replicate the points 9 times if you want tori topology. Sariel.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-48263211878195128932013-01-09T13:54:44.182-05:002013-01-09T13:54:44.182-05:00It would be easier if you worked with Delaunay tri...It would be easier if you worked with Delaunay triangulations instead of Voronoi diagrams, particularly if all you want is the area of the Voronoi region, which can be extracted quite readily from the DT. Deleting a point from a 2-d triangulation is quite simple if you have access to primitives for 2-2 flips and 3-1 flips. Try Shewchuk's code. <br />OINKYnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-81213504933027019622013-01-09T12:27:54.258-05:002013-01-09T12:27:54.258-05:00What are your accuracy requirements? I suspect one...What are your accuracy requirements? I suspect one could come with some approximate version based on kd trees based nearest neighbor data structures. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-12160901366516205282013-01-09T11:18:41.443-05:002013-01-09T11:18:41.443-05:00Eric --
My cases won't be worst cases, so I&#...Eric --<br /><br />My cases won't be worst cases, so I'd like something that has good "average case" performance (like randomized incremental algorithms should on insertions, but also for deletions). <br /><br />Similarly, vor++ seems maybe a little loose on how it handles degenerate cases -- but I don't really care about degenerate cases.Michael Mitzenmacherhttp://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-52026581698718231022013-01-09T11:14:05.807-05:002013-01-09T11:14:05.807-05:00Isn't dynamic insertion and deletion necessari...Isn't dynamic insertion and deletion necessarily Omega(n) at least? Consider n-1 points on a circle, and repeatedly inserting and deleting the center of the circle. Each insertion changes all n-1 Voronoi cells.Eric Pricehttp://www.blogger.com/profile/07442856297755779553noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-84505805644178566132013-01-09T08:44:29.888-05:002013-01-09T08:44:29.888-05:00Anon:
I had a student look at this and he had bee...Anon:<br /><br />I had a student look at this and he had been working with Voro++. It doesn't handle deletions on its own but he suggested the code could be modified to handle it. Though, truthfully, it seemed a bit slow -- I might be able to handle experiments with 1000 points, but not 10000. <br /><br />But that might be the way to go.<br /><br />Michael Mitzenmacherhttp://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-20875443237459388282013-01-09T08:13:37.968-05:002013-01-09T08:13:37.968-05:00How about http://math.lbl.gov/voro++/about.html?
...How about http://math.lbl.gov/voro++/about.html? <br /><br />They seem to support tori, though I am not sure about its dynamic behavior. Beyond: It maybe problematic if you're aiming at exact constructions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-79049733434906867972013-01-09T07:51:12.249-05:002013-01-09T07:51:12.249-05:00I'll check, but I don't think any of these...I'll check, but I don't think any of these things support dynamic deletion of points. (I don't think the C++ numerical recipes does either, though I'm finding it a bit hard to tell -- may need a more careful read.) And Kevin, I intend (as usual) to be thrashing the code, so even at few thousand points, I think the difference will be something like 3 orders of magnitude in time, so that's the difference between finishing experiments in a day or in a year...<br /><br />I forgot one other desiderata -- I'd really like for the code to do this for points "on the unit torus", just because I like symmetry, and to make the problem even harder. Will add to the original post.Michael Mitzenmacherhttp://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-2148612378264364752013-01-09T05:32:12.711-05:002013-01-09T05:32:12.711-05:00try C++ numerical recipes 3rd edition page 1145try C++ numerical recipes 3rd edition page 1145Josh Reubenhttp://www.blogger.com/profile/02914970554397831060noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-88619023482063323582013-01-09T04:39:32.092-05:002013-01-09T04:39:32.092-05:00http://cran.r-project.org/web/packages/deldir/inde...http://cran.r-project.org/web/packages/deldir/index.html<br /><br />I used it once three years ago. He won't get the volumes<br /> of each cell though (but for each tile he can bound it by the<br />volume of the sphere passing by the d+1 edges further<br />from the center)<br /><br />tile.list<br />tile.centroids<br />deldir<br />kavehhttp://www.blogger.com/profile/16832727483199371359noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-43028877259986799532013-01-09T02:35:24.759-05:002013-01-09T02:35:24.759-05:00The first libraries that come to mind are CGAL (cg...The first libraries that come to mind are CGAL (cgal.org) and Qhull (qhull.org).<br /><br />AFAIK neither supports dynamic addition or deletion of points. But Voronoi diagrams are O(n log n), so if you have only a few thousand points and a multi-gigahertz machine, recomputing everything from scratch may be plenty fast.Kevinhttp://www.blogger.com/profile/13315715886823365629noreply@blogger.com