{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:25:27Z","timestamp":1760441127884},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2013,7]]},"DOI":"10.1007\/s00454-013-9486-0","type":"journal-article","created":{"date-parts":[[2013,5,31]],"date-time":"2013-05-31T11:28:01Z","timestamp":1369999681000},"page":"124-184","source":"Crossref","is-referenced-by-count":7,"title":["An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains"],"prefix":"10.1007","volume":"50","author":[{"given":"Lyudmil","family":"Aleksandrov","sequence":"first","affiliation":[]},{"given":"Hristo","family":"Djidjev","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"J\u00f6rg-R\u00fcdiger","family":"Sack","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,6,1]]},"reference":[{"key":"9486_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Sharathkumar, R., Yu, H.: Approximate Euclidean shortest paths amid convex obstacles. In C. Mathieu (ed.) SODA, pp. 283\u2013292. SIAM, New York (2009)","DOI":"10.1137\/1.9781611973068.32"},{"key":"9486_CR2","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1145\/335305.335339","volume-title":"STOC","author":"L Aleksandrov","year":"2000","unstructured":"Aleksandrov, L., Maheshwari, A., Sack, J.-R.: Approximation algorithms for geometric shortest path problems. In: Yao, F.F., Luks, E.M. (eds.) STOC, pp. 286\u2013295. ACM, New York (2000)"},{"issue":"1","key":"9486_CR3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1044731.1044733","volume":"52","author":"L Aleksandrov","year":"2005","unstructured":"Aleksandrov, L., Maheshwari, A., Sack, J.-R.: Determining approximate shortest paths on weighted polyhedral surfaces. J. ACM 52(1), 25\u201353 (2005)","journal-title":"J. ACM"},{"issue":"4","key":"9486_CR4","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1007\/s00454-009-9204-0","volume":"44","author":"L Aleksandrov","year":"2010","unstructured":"Aleksandrov, L., Djidjev, H., Guo, H., Maheshwari, A., Nussbaum, D., Sack, J.-R.: Algorithms for approximate shortest path queries on weighted polyhedral surfaces. Discrete Comput. Geom. 44(4), 762\u2013801 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9486_CR5","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00454-003-2952-3","volume":"31","author":"T Asano","year":"2004","unstructured":"Asano, T., Kirkpatrick, D., Yap, C.: Pseudo approximation algorithms with applications to optimal motion planning. Discrete Comput. Geom. 31(1), 139\u2013171 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9486_CR6","unstructured":"Aurenhammer, F., Klein, R.: Handbook of Computational Geometry. Chapter Voronoi Diagrams. North Holland, Amsterdam (2000)"},{"key":"9486_CR7","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF02187906","volume":"3","author":"CL Balaji","year":"1988","unstructured":"Balaji, C.L.: The algebraic degree of geometric optimization problems. Discrete Comput. Geom. 3, 177\u2013191 (1988)","journal-title":"Discrete Comput. Geom."},{"key":"9486_CR8","doi-asserted-by":"crossref","unstructured":"Canny, J.F., Reif, J.H.: New lower bound techniques for robot motion planning problems. In: FOCS, pp. 49\u201360. IEEE Computer Society, Los Alamitos (1987)","DOI":"10.1109\/SFCS.1987.42"},{"issue":"4","key":"9486_CR9","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1142\/S0218195997000181","volume":"7","author":"J Choi","year":"1997","unstructured":"Choi, J., Sellen, J., Yap, C.-K.: Approximate Euclidean shortest paths in 3-space. Int. J. Comput. Geom. Appl. 7(4), 271\u2013295 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"5","key":"9486_CR10","doi-asserted-by":"crossref","first-page":"1577","DOI":"10.1137\/S0097539798340205","volume":"29","author":"J Choi","year":"2000","unstructured":"Choi, J., Sellen, J., Yap, C.-K.: Precision-sensitive Euclidean shortest path in 3-space. SIAM J. Comput. 29(5), 1577\u20131595 (2000)","journal-title":"SIAM J. Comput."},{"key":"9486_CR11","first-page":"56","volume-title":"STOC","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L.: Approximation algorithms for shortest path motion planning (extended abstract). In: Aho, A.V. (ed.) STOC, pp. 56\u201365. ACM, New York (1987)"},{"issue":"2","key":"9486_CR12","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1109\/TMI.2009.2032358","volume":"29","author":"B Cox","year":"2010","unstructured":"Cox, B., Treeby, B.: Artifact trapping during time reversal photoacoustic imaging for acoustically heterogeneous media. IEEE Trans. Med. Imaging 29(2), 387\u2013396 (2010)","journal-title":"IEEE Trans. Med. Imaging"},{"issue":"4","key":"9486_CR13","doi-asserted-by":"crossref","first-page":"1182","DOI":"10.1137\/S0097539797325223","volume":"28","author":"S Har-Peled","year":"1999","unstructured":"Har-Peled, S.: Constructing approximate shortest path maps in three dimensions. SIAM J. Comput. 28(4), 1182\u20131197 (1999)","journal-title":"SIAM J. Comput."},{"key":"9486_CR14","doi-asserted-by":"crossref","unstructured":"Hilaga, M., Shinagawa, Y., Komura, T., Kunii, T.L.: Topology matching for fully automatic similarity estimation of 3d shapes. In: SIGGRAPH, pp. 203\u2013212 (2001)","DOI":"10.1145\/383259.383282"},{"issue":"3","key":"9486_CR15","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1093\/cercor\/bhp127","volume":"20","author":"K Im","year":"2010","unstructured":"Im, K., Jo, H.J., Mangin, J.-F., Evans, A.C., Kim, S.I., Lee, J.-M.: Spatial distribution of deep sulcal landmarks and hemispherical asymmetry on the cortical surface. Cereb. Cortex 20(3), 602\u2013611 (2010)","journal-title":"Cereb. Cortex"},{"key":"9486_CR16","volume-title":"Fundamentals of Seismic Tomography. Geophysical Monograph Series, vol. 6","author":"PL Inderwiesen","year":"1994","unstructured":"Inderwiesen, P.L., Lo, T.-W.: Fundamentals of Seismic Tomography. Geophysical Monograph Series, vol. 6. Society of Exploration Geophysicists, Tarnaka (1994)"},{"key":"9486_CR17","first-page":"148","volume-title":"Graphics Interface","author":"T Kanai","year":"1999","unstructured":"Kanai, T., Suzuki, H., Mitani, J., Kimura, F.: Interactive mesh fusion based on local 3d metamorphosis. In: MacKenzie, I.S., Stewart, J. (eds.) Graphics Interface, pp. 148\u2013156. Canadian Human\u2013Computer Communications Society, St. John\u2019s (1999)"},{"issue":"2","key":"9486_CR18","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/38.824544","volume":"20","author":"T Kanai","year":"2000","unstructured":"Kanai, T., Suzuki, H., Kimura, F.: Metamorphosis of arbitrary triangular meshes. IEEE Comput. Graph. Appl. 20(2), 62\u201375 (2000)","journal-title":"IEEE Comput. Graph. Appl."},{"key":"9486_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science, vol. 400","author":"R Klein","year":"1989","unstructured":"Klein, R.: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science, vol. 400. Springer, Berlin (1989)"},{"issue":"9","key":"9486_CR20","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi diagrams revisited. Comput. Geom. 42(9), 885\u2013902 (2009)","journal-title":"Comput. Geom."},{"key":"9486_CR21","doi-asserted-by":"crossref","unstructured":"Krozel, J., Penny, S., Prete, J., Mitchell, J.S.B.: Comparison of algorithms for synthesizing weather avoidance routes in transition airspace. In Collection of Technical Papers\u2014AIAA Guidance, Navigation, and Control Conference, vol. 1, pp. 446\u2013461 (2004)","DOI":"10.2514\/6.2004-4790"},{"issue":"4","key":"9486_CR22","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s00453-001-0027-5","volume":"30","author":"M Lanthier","year":"2001","unstructured":"Lanthier, M., Maheshwari, A., Sack, J.-R.: Approximating shortest paths on weighted polyhedral surfaces. Algorithmica 30(4), 527\u2013562 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"9486_CR23","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.jcss.2003.06.002","volume":"68","author":"N-M L\u00ea","year":"2004","unstructured":"L\u00ea, N.-M.: Abstract Voronoi diagram in 3-space. J. Comput. Syst. Sci. 68(1), 41\u201379 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9486_CR24","doi-asserted-by":"crossref","unstructured":"Lee, A., Dobkin, D., Sweldens, W., Schr\u00f6der, P.: Multiresolution mesh morphing. In: Proceedings of SIGGRAPH 99, pp. 343\u2013350, August 1999","DOI":"10.1145\/311535.311586"},{"key":"9486_CR25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/978-1-4613-8369-7_3","volume-title":"Graphs Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and Its Application, vol. 56","author":"GL Miller","year":"1993","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Automatic mesh partitioning. In: Alan, G., John, G., Joseph, L. (eds.) Graphs Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and Its Application, vol. 56, pp. 57\u201384. Springer, Berlin (1993)"},{"issue":"1","key":"9486_CR26","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/102782.102784","volume":"38","author":"JSB Mitchell","year":"1991","unstructured":"Mitchell, J.S.B., Papadimitriou, C.H.: The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM 38(1), 18\u201373 (1991)","journal-title":"J. ACM"},{"key":"9486_CR27","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B., Sharir, M.: New results on shortest paths in three dimensions. In: Snoeyink, J., Boissonnat, J.-D. (eds.) Symposium on Computational Geometry, pp. 124\u2013133. ACM, New York (2004)","DOI":"10.1145\/997817.997839"},{"key":"9486_CR28","first-page":"394","volume-title":"ISCIS. Lecture Notes in Computer Science, vol. 4263","author":"C Ozmen","year":"2006","unstructured":"Ozmen, C., Balcisoy, S.: A framework for working with digitized cultural heritage artifacts. In: Levi, A., Savas, E., Yenig\u00fcn, H., Balcisoy, S., Saygin, Y. (eds.) ISCIS. Lecture Notes in Computer Science, vol. 4263, pp. 394\u2013400. Springer, Berlin (2006)"},{"issue":"5","key":"9486_CR29","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0020-0190(85)90029-8","volume":"20","author":"CH Papadimitriou","year":"1985","unstructured":"Papadimitriou, C.H.: An algorithm for shortest-path motion in three dimensions. Inf. Process. Lett. 20(5), 259\u2013263 (1985)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9486_CR30","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s00453-003-1079-5","volume":"39","author":"JH Reif","year":"2004","unstructured":"Reif, J.H., Sun, Z.: Movement planning in the presence of flows. Algorithmica (New York) 39(2), 127\u2013153 (2004)","journal-title":"Algorithmica (New York)"},{"key":"9486_CR31","doi-asserted-by":"crossref","unstructured":"Sun, Z., Reif, J.: Bushwhack: an approximation algorithm for minimal paths through pseudo-Euclidean spaces. In: Eades, P., Takaoka, T. (eds.) Algorithms and Computation. Lecture Notes in Computer Science, vol. 2223, pp. 160\u2013171. Springer, Berlin (2001). doi: 10.1007\/3-540-45678-3_15","DOI":"10.1007\/3-540-45678-3_15"},{"issue":"1","key":"9486_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.07.004","volume":"58","author":"Z Sun","year":"2006","unstructured":"Sun, Z., Reif, J.H.: On finding approximate optimal paths in weighted regions. J. Algorithms 58(1), 1\u201332 (2006)","journal-title":"J. Algorithms"},{"issue":"9","key":"9486_CR33","doi-asserted-by":"crossref","first-page":"1473","DOI":"10.1109\/TUFFC.2005.1516019","volume":"52","author":"T Varslot","year":"2005","unstructured":"Varslot, T., Taralsen, G.: Computer simulation of forward wave propagation in soft tissue. IEEE Trans. Ultrason. Ferroelectr. Freq. Control 52(9), 1473\u20131482 (2005)","journal-title":"IEEE Trans. Ultrason. Ferroelectr. Freq. Control"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9486-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-013-9486-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9486-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T05:24:55Z","timestamp":1563081895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-013-9486-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["9486"],"URL":"https:\/\/doi.org\/10.1007\/s00454-013-9486-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,1]]}}}