Timeline for $n$-dimensional Voronoi diagram
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 24, 2022 at 11:30 | history | suggested | The Amplitwist | CC BY-SA 4.0 |
fixed broken link to springerlink.com; added full citation in tooltip; fixed broken link to polymake; added name of module instead of "this"
|
| Sep 24, 2022 at 9:45 | review | Suggested edits | |||
| S Sep 24, 2022 at 11:30 | |||||
| Aug 3, 2022 at 11:04 | history | edited | Glorfindel | CC BY-SA 4.0 |
broken link fixed
|
| Jun 6, 2017 at 12:18 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Broken link replaced by CRC link.
|
| Apr 5, 2013 at 5:12 | comment | added | Adel Ahmadyan | I'm afraid it is as bad as Allessandro fears. The main problem is the number of the hyperplanes that these algorithm generates. For a very simple example, I used qhull for 40 points in 15-d and the voronoi decomposition has more than 5 million hyperplanes Voronoi diagram by the convex hull of 40 points in 16-d: Number of Voronoi regions: 40 Number of Voronoi vertices: 1361237 Statistics for: rbox 40 s D15 | qvoronoi s p TO test Number of points processed: 40 Number of hyperplanes created: 5539466 Number of facets in hull: 2774645 Number of distance tests for qhull: 4729150 | |
| Dec 15, 2010 at 15:06 | history | edited | Joseph O'Rourke | CC BY-SA 2.5 |
Another typo.
|
| Dec 15, 2010 at 14:10 | comment | added | Joseph O'Rourke | @Alessandro: It may not be as bad as you fear. See, e.g., "Higher-dimensional Voronoi diagrams in linear expected time," by Rex Dwyer, and track papers that cite this into the future. portal.acm.org/citation.cfm?id=73869 | |
| Dec 15, 2010 at 14:05 | comment | added | Alessandro | Thank you very much for your answer! I read some more about the topic and indeed it seems quite complex. Furthermore, the run-time complexity of the algorithms is probably too high for my needs -I would like not to go over the n^2 worst case complexity. Do you know of any fast approximate algorithms that can help me? | |
| Dec 15, 2010 at 13:57 | vote | accept | Alessandro | ||
| Dec 15, 2010 at 13:11 | history | edited | Joseph O'Rourke | CC BY-SA 2.5 |
added 82 characters in body
|
| Dec 15, 2010 at 13:05 | history | answered | Joseph O'Rourke | CC BY-SA 2.5 |