O(n) Fast Marching Methods: Implementation and Comparison
Contents:
Author
- Pablo Muñóz
- Score: 8.4/10
Objective
There are many different Fast Marching Method (FMM) versions. Some of them are O(n log n) (with n as the number of cells of the map). Others are O(n). Altuogh the literature includes some comparisons among different methods, there is not a exahustive comparison including all of the algorithms.
In this project, the 6 different versions known (all we were able to find) are implemented, impartially, and exahustively compared.
Results
Time comparison for a 2D grid with start in the center.
Time comparison for a 3D grid with start in the center.
Example of one of the FMM versions solving a maze.