Wow literally just what I needed to see for a project I’m working on, I love hacker news!
I'd advise to look into Jonathan Shewchuk's work which is very accessible.
Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
11–20 of 34 posts
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#12I would be interested in an explanation why it's O(nlog(n)). It requires sorting the points along one axis which already gives O(nlog(n)) as a lower bound, but I'd be interested in how the line-sweeping would need to be done to not go over that. The number of points in the beach front should roughly scale with the square root of points, so a naive search/replace per point insertion would take sqrt(n) operations and a…
The complexities don't multiply here. The complexities would only
multiply if you had to sort for EACH of something. We're only doing a single sort.
> sorting the points along one axis which already gives O(nlog(n))
You're looking at it backwards, this is actually good news! It means that any subsequent work we do of similar or lower complexity doesn't change anything.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#13I would be interested in an explanation why it's O(nlog(n)). It requires sorting the points along one axis which already gives O(nlog(n)) as a lower bound, but I'd be interested in how the line-sweeping would need to be done to not go over that. The number of points in the beach front should roughly scale with the square root of points, so a naive search/replace per point insertion would take sqrt(n) operations and a…
The complexities don't multiply here. The complexities would only multiply if you had to sort for EACH of something. We're only doing a single sort. > sorting the points along one axis which already gives O(nlog(n)) You're looking at it backwards, this is actually good news! It means that any subsequent work we do of similar or lower complexity doesn't change anything.
>The complexities don't multiply here.
I never said that. I just mentioned that O(n log(n)) is the lower bound since sorting will already take that long.
What I'm concerned with is the complexity of the scanning step, which I think might be more than O(n log(n)) on its own (and therefore more than O(n log(n)) overall)
At least I'd like to see an explanation why it's <= O(n log(n))
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#14Unfortunately, as you move into higher dimensions, these algorithms typically bog down. Suppose that you have a point that is inside of the convex hull of the mesh that you want to use for triangulation (we‘re talking hyper-triangles here). What are the best points to choose for your triangulation? Since there are a lot of candidates for hyper-triangles you cannot possibly store the set of triangles beforehand. I app…
Could you not do dimensional reduction first, run the algorithm on the first X components, map the result back onto the loadings?
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#15One 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…
I think convex hull is also closely related.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#16I wrote a moderately popular Delaunay/Voronoi library for Unity a few years back [1] with a neat little demo video [2]. I implemented the incremental Bowyer-Watson algorithm for generating the triangulations, and then took the dual to generate the Voronoi tesselation (I also added a "clipper" that clips the voronoi diagram to a convex outline, which was fun, I haven't seen that anywhere else before and had to figure out how to do it myself).
Bowyer-Watson (which is described in this article) seems very simple to implement when you start: just start with a "big triangle" and then add points iteratively to it, and perform the flips you need to do. To do it performant, you have to build up a tree structure as you go, but it's not very tricky.
However: almost every description (including on Wikipedia) and implementation of Bowyer-Watson I could find was wrong. There's an incredibly subtle and hard to deal with issue with the algorithm, which is the initial "big triangle". Most people who implement it (and indeed I did the same initally) just make the triangle big enough to contain all the points, but that's not enough: it needs to be big enough to contain all the points in all the circumcircles of the triangles. These circumcircles can get ENORMOUS: in the limit of three points on a line, it's an infinite half-plane. Even if they aren't literally collinear, just close, the triangle becomes way to huge to deal with.
The answer is that you have to put the points "at infinity", which is a very weird concept. Basically, you have to have special rules for these points when doing comparisons, it's really tricky and very hard to get right.
If I were doing this again, I wouldn't use Bowyer-Watson, this subtlety is too tricky and hard to get right. Fortune's sweep-line is more complex on the surface, but that's the one I would go with. Or the 3D convex hull technique (which I also wrote a library for, by the way [3]).
[1]: https://github.com/OskarSigvardsson/unity-delaunay
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#17Unfortunately, as you move into higher dimensions, these algorithms typically bog down. Suppose that you have a point that is inside of the convex hull of the mesh that you want to use for triangulation (we‘re talking hyper-triangles here). What are the best points to choose for your triangulation? Since there are a lot of candidates for hyper-triangles you cannot possibly store the set of triangles beforehand. I app…
Could you not do dimensional reduction first, run the algorithm on the first X components, map the result back onto the loadings?
Most triangulation algorithms are designed for the two-dimensional plane, so this only works if the first two components are sufficient.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#18One 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…
I think convex hull is also closely related.
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)) (2020)
#19In case anyone wonders how a voronoi diagram looks on a wall, here's my living room https://tomk32.de/assets/voronoi-wall.jpg
The process to create it is as simple as you might think, select points, draw the center lines for all pairs of close neighbour points and the corners will appear naturally. Tape all edges and paint the wall starting with almost white, mix more of the three base colours into for each of the cells.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#20I would be interested in an explanation why it's O(nlog(n)). It requires sorting the points along one axis which already gives O(nlog(n)) as a lower bound, but I'd be interested in how the line-sweeping would need to be done to not go over that. The number of points in the beach front should roughly scale with the square root of points, so a naive search/replace per point insertion would take sqrt(n) operations and a…
Just like many other sweep line based algorithms, you need to store the beach within an appropriate binary search tree that's log(n) per tree operation. And the total amount of tree queries should be proportional to the number of features (faces, edges, vertices) within Delaunay Triangulation. The fact that amount of features within triangulation is proportional to the number of vertices can be proved using Euler's formula F+V-E=2. V=n, E=F*3/2 (each triangle has 3 edges, but each edge is shared by 2 faces).