[ginko]

I 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 O(n*sqrt(n)) overall runtime.

[Karliss]

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

[stravant]

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.

[ginko]

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