Re:Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) ...
by hyperific on Wednesday October 25, 2023 @03:46AM
(#38010307)
Super cool resource! Thanks for sharing this!
Re:Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) ...
by eutectic on Wednesday October 25, 2023 @04:52AM
(#38010710)
I think convex hull is also closely related.
Re:Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) ...
by OskarS on Wednesday October 25, 2023 @05:43AM
(#38011030)
Indeed: the convex hull is the outer boundary of the Delaunay triangulation. In addition: if you "bow out" the points into 3D, the 3D convex hull is exactly the Delaunay triangulation. These two concepts are very closely related.
Re:Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) ...
by kian on Wednesday October 25, 2023 @07:03PM
(#38019478)
This is pure speculation (graphics algorithms and geometry aren't my strengths), but if you were to do this with a set of 3d points, would we get a relationship between delaunay triangulation (pyramidalization / convex hull?) a relative neighborhood graph, and a minimum spanning tree of 3d points, where combining the RNG and the MST would yield between 1 and 8 edges coming out? (at which point, we could use, say, the numpad for 3d gui widget navigation in the meta-verse in the same way you suggest using 4 cardinal directions for 2d gui representations)
Re:Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) ...
by emmanueloga_ on Thursday October 26, 2023 @05:26AM
(#38023483)
Interesting question! By virtue of being a tree, the MST produces at most 3 edges coming out of any vertex, so this should be the same in 3D. The MST then adds (sometimes) a 4th edge, so, although you could build both graphs in 3D space, you would still end up with 4 edges coming out of any vertex, I think.
In 3D space the Delaunay triangulation would produce a bunch of irregular tetrahedra, so the edges coming out from every vertex would vary between a minimum of 3, and a maximum of 12, if I get it right (ref: [1] :-).
The 3D Voronoi cells are another story... I found some implementation that you can play with to see how it looks [2] [3], each cell is of a shape called "convex polytope". It feels like these cells are packed like each of the sub-cubes of a rubik, but I'm not 100% sure :-) ... if that's true, you could jump from each vertex to the next in at most 26 directions? (hand-waves :-p)
--
1: https://en.wikipedia.org/wiki/Tetrahedron#/media/File:M_tic....
I have a theory that the union of the edges of the RNG and EMSP could be used for automatic navigation between widgets in a GUI: combining the two, there's always between 1 and 4 edges coming out of every point, and so each of them could correspond to a direction key up/down/left/right according to some simple heuristic.
--
1: https://axltnnr.io/2018/Triangulation/