search

joshheinrichs / delaunay-triangulation

An application built for real-time rendering and analysis of Delaunay triangulations.
1 stars 1 forks source link

Optimize Shortest Paths Between Vertexes #18

Open joshheinrichs opened 9 years ago

joshheinrichs commented 9 years ago

Currently, all vertexes are finding the shortest path to all other vertexes using Djikstra's algorithm. This means that it has a O(n^3log(n)) running time. This can be reduced down to O(n^2).

joshheinrichs commented 9 years ago

Probably not relevant for the moment, since only point to point distance is required. This feature will likely be cut.