O(N) implementation of the fast marching algorithm. Yatziv, L., Bartesaghi, A., & Sapiro, G. 2006.
O(N) implementation of the fast marching algorithm [link]Website  abstract   bibtex   
In this note we present an implementation of the fast marching algorithm for solving Eikonal equations that in practice reduces the original run-time from O(N log N) to linear. This lower run-time cost is obtained while keeping an error bound of the same order of magnitude as the original algorithm. This improvement is achieved introducing the straight forward untidy priority queue, obtained via a quantization of the priorities in the marching computation. We present the underlying framework, estimations on the error, and examples showing the usefulness of the proposed approach.
@misc{
 title = {O(N) implementation of the fast marching algorithm},
 type = {misc},
 year = {2006},
 source = {Journal of Computational Physics},
 identifiers = {[object Object]},
 keywords = {Bucket sort,Distance functions,Fast marching,Hamilton-Jacobi and Eikonal equations,Untidy priority queue},
 pages = {393-399},
 volume = {212},
 issue = {2},
 websites = {http://www.sciencedirect.com/science/article/pii/S0021999105003736},
 id = {bc5f74d3-a304-339b-bca0-72a01ec519eb},
 created = {2015-05-07T14:40:12.000Z},
 file_attached = {false},
 profile_id = {5477662f-c7a8-37b0-902d-765da20fee71},
 last_modified = {2018-01-19T17:11:42.772Z},
 read = {false},
 starred = {false},
 authored = {true},
 confirmed = {true},
 hidden = {false},
 citation_key = {Yatziv2006},
 folder_uuids = {644af951-328a-4794-8436-dbab34dfd4ee},
 private_publication = {false},
 abstract = {In this note we present an implementation of the fast marching algorithm for solving Eikonal equations that in practice reduces the original run-time from O(N log N) to linear. This lower run-time cost is obtained while keeping an error bound of the same order of magnitude as the original algorithm. This improvement is achieved introducing the straight forward untidy priority queue, obtained via a quantization of the priorities in the marching computation. We present the underlying framework, estimations on the error, and examples showing the usefulness of the proposed approach.},
 bibtype = {misc},
 author = {Yatziv, Liron and Bartesaghi, Alberto and Sapiro, Guillermo}
}
Downloads: 0