{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:24:04Z","timestamp":1787329444601,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>This paper presents an efficient, fine-grained parallel algorithm for solving the Eikonal equation on triangular meshes. The Eikonal equation, and the broader class of Hamilton\u2013Jacobi equations to which it belongs, have a wide range of applications from geometric optics and seismology to biological modeling and analysis of geometry and images. The ability to solve such equations accurately and efficiently provides new capabilities for exploring and visualizing parameter spaces and for solving inverse problems that rely on such equations in the forward model. Efficient solvers on state-of-the-art, parallel architectures require new algorithms that are not, in many cases, optimal, but are better suited to synchronous updates of the solution. In previous work [W. K. Jeong and R. T. Whitaker, SIAM J. Sci. Comput., 30 (2008), pp. 2512\u20132534], the authors proposed the fast iterative method (FIM) to efficiently solve the Eikonal equation on regular grids. In this paper we extend the fast iterative method to solve Eikonal equations efficiently on triangulated domains on the CPU and on parallel architectures, including graphics processors. We propose a new local update scheme that provides solutions of first-order accuracy for both architectures. We also propose a novel triangle-based update scheme and its corresponding data structure for efficient irregular data mapping to parallel single-instruction multiple-data (SIMD) processors. We provide detailed descriptions of the implementations on a single CPU, a multicore CPU with shared memory, and SIMD architectures with comparative results against state-of-the-art Eikonal solvers.<\/jats:p>","DOI":"10.1137\/100788951","type":"journal-article","created":{"date-parts":[[2011,10,7]],"date-time":"2011-10-07T18:46:57Z","timestamp":1318013217000},"page":"2468-2488","source":"Crossref","is-referenced-by-count":45,"title":["A Fast Iterative Method for Solving the Eikonal Equation on Triangulated Surfaces"],"prefix":"10.1137","volume":"33","author":[{"given":"Zhisong","family":"Fu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Won-Ki","family":"Jeong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yongsheng","family":"Pan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert M.","family":"Kirby","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ross T.","family":"Whitaker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,10,6]]},"reference":[{"key":"R1","unstructured":"CUDA Occupancy Calculator\n                      , available online at http:\/\/developer.download.nvidia.com\/compute\/cuda\/CUDA_Occupancy_calculator.xls."},{"key":"R2","unstructured":"D. Bertsekas,\n                      Dynamic Programming and Optimal Control\n                      , Athena Scientific, Belmont, MA, 1995."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-006-0016-y"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015800"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(93)90001-Q"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442644"},{"key":"R7","unstructured":"M. Falcone,\n                      The minimum time problem and its applications to front propagation\n                      , in Motion by Mean Curvature and Related Topics, de Gruyter, Berlin, 1994, pp. 70\u201388."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J. E. Greivenkamp,\n                      Field Guide to Geometrical Optics\n                      , SPIE Publications, Bellingham, WA, 2003.","DOI":"10.1117\/3.547461"},{"key":"R9","unstructured":"M. Herrmann,\n                      A domain decomposition parallelization of the fast marching method\n                      , in Center for Turbulence Research Annual Research Briefs, Stanford University, Stanford, CA, 2003, pp. 213\u2013225."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70571"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/060670298"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00163916"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.15.8431"},{"key":"R15","unstructured":"NVIDIA,\n                      NVIDIA CUDA C Programming Guide\n                      , available online at http:\/\/developer.nvidia.com\/nvidia-gpu-computing-documentation.html."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"E. Pichon and A. Tannenbaum,\n                      Curve segmentation using directional information, relation to pattern detection\n                      , in ICIP Volume 2, Genoa, Italy, 2005, pp. 794\u2013797.","DOI":"10.1109\/ICIP.2005.1530175"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/9.661081"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/050627083"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1190\/1.1443263"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-246X.2004.02153.x"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0729053"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.4.1591"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"R. Sheriff and L. Geldart,\n                      Exploration Seismology\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9781139168359"},{"key":"R24","unstructured":"O. Sifri, A. Sheffer, and C. Gotsman,\n                      Geodesic-based surface remeshing\n                      , in Proceedings of the IMR, Kuala Lumpur, Malaysia, 2003, pp. 189\u2013199."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.4171\/IFB\/102"},{"key":"R26","unstructured":"T. Srinark and C. Kambhamettu,\n                      A novel method for 3D surface mesh segmentation\n                      , in Computer Graphics and Imaging, IASTED\/ACTA Press, Calgary, Canada, 2003, pp. 212\u2013217."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142901396533"},{"key":"R28","unstructured":"M. C. Tugurlan,\n                      Fast Marching Methods-Parallel Implementation and Analysis\n                      , Ph.D. thesis, Louisiana State University, Baton Rouge, LA, 2008."},{"key":"R29","unstructured":"Wikipedia,\n                      Supercomputer\n                      , available online at http:\/\/en.wikipedia.org\/wiki\/Supercomputer."},{"key":"R30","unstructured":"H. Zhang, O. V. Kaick, and R. Dyer,\n                      Spectral methods for mesh processing and analysis\n                      , in STAR Proceedings of Eurographics 2007, D. Schmalstieg and J. Bittner, eds., Prague, 2007, Eurographics Association, Geneva, Switzerland, pp. 1\u201322."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-04-01678-3"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100788951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:17:51Z","timestamp":1787325471000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100788951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100788951"],"URL":"https:\/\/doi.org\/10.1137\/100788951","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}