|
|
|
|
|
|
by Karliss
965 days ago
|
|
|
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). |
|
|