Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)

codeforces.com

Post reply on HN
Print view View original

31–34 of 34 posts

Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)

#31

Post by Rhapso »

amelius wrote: post #26
Rhapso wrote: post #25

Earlier quoted context omitted.

Ah, I'm an engineer not a theorist. Such degenerate input is unlikely to be a valid use case, can be detected, and I can reject it. Wait until you see the actual heuristic I use for solving voronoi/delaunay in arbitrary topologies. I need to write a blog post on it anyways.

It's very easy to get 4 points on a circle. In 2d space just the four corners of a unit square would do it.

On a sphere or modulus space, that just becomes a K4, so it isn't even an edge case, it is the solution that the approximation would generate.

Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)

#32

Post by amelius »

Rhapso wrote: post #31
amelius wrote: post #26

Earlier quoted context omitted.

It's very easy to get 4 points on a circle. In 2d space just the four corners of a unit square would do it.

On a sphere or modulus space, that just becomes a K4, so it isn't even an edge case, it is the solution that the approximation would generate.

Yes, you definitely have to deal with it, in virtually any setup.

Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)

#33

Post by kian »

emmanueloga_ wrote: post #3

One of my favorite renderings of this is in this article [1], that shows the relationship between the Delaunay triangulation, Voronoi diagram, a relative neighborhood graph (RNG) and the euclidean minimum spanning tree (EMSP) of a set of 2d points. 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…

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)) (2020)

#34

Post by emmanueloga_ »

kian wrote: post #33
emmanueloga_ wrote: post #3

One of my favorite renderings of this is in this article [1], that shows the relationship between the Delaunay triangulation, Voronoi diagram, a relative neighborhood graph (RNG) and the euclidean minimum spanning tree (EMSP) of a set of 2d points. 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…

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…

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....

2: https://github.com/BrunoLevy/geogram/wiki/Delaunay3D

3: https://math.lbl.gov/voro++/examples/

Post reply on HN