Remarks on the O(N) Implementation of the Fast Marching Method
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2007
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911217086365696 |
|---|---|
| author | Rasch, Christian Satzger, Thomas |
| author_facet | Rasch, Christian Satzger, Thomas |
| contents | The fast marching algorithm computes an approximate solution to the eikonal equation in O(N log N) time, where the factor log N is due to the administration of a priority queue. Recently, Yatziv, Bartesaghi and Sapiro have suggested to use an untidy priority queue, reducing the overall complexity to O(N) at the price of a small error in the computed solution. In this paper, we give an explicit estimate of the error introduced, which is based on a discrete comparison principle. This estimates implies in particular that the choice of an accuracy level that is independent of the speed function F results in the complexity bound O(Fmax /Fmin N). A numerical experiment illustrates this robustness problem for large ratios Fmax /Fmin . |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0703082 |
| institution | arXiv |
| publishDate | 2007 |
| record_format | arxiv |
| spellingShingle | Remarks on the O(N) Implementation of the Fast Marching Method Rasch, Christian Satzger, Thomas Numerical Analysis The fast marching algorithm computes an approximate solution to the eikonal equation in O(N log N) time, where the factor log N is due to the administration of a priority queue. Recently, Yatziv, Bartesaghi and Sapiro have suggested to use an untidy priority queue, reducing the overall complexity to O(N) at the price of a small error in the computed solution. In this paper, we give an explicit estimate of the error introduced, which is based on a discrete comparison principle. This estimates implies in particular that the choice of an accuracy level that is independent of the speed function F results in the complexity bound O(Fmax /Fmin N). A numerical experiment illustrates this robustness problem for large ratios Fmax /Fmin . |
| title | Remarks on the O(N) Implementation of the Fast Marching Method |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/cs/0703082 |