{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:48:06Z","timestamp":1763466486499,"version":"3.37.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,7,7]],"date-time":"2009-07-07T00:00:00Z","timestamp":1246924800000},"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":[[2010,12]]},"DOI":"10.1007\/s00454-009-9204-0","type":"journal-article","created":{"date-parts":[[2009,7,6]],"date-time":"2009-07-06T19:04:05Z","timestamp":1246907045000},"page":"762-801","source":"Crossref","is-referenced-by-count":23,"title":["Algorithms for Approximate Shortest Path Queries on\u00a0Weighted Polyhedral Surfaces"],"prefix":"10.1007","volume":"44","author":[{"given":"Lyudmil","family":"Aleksandrov","sequence":"first","affiliation":[]},{"given":"Hristo N.","family":"Djidjev","sequence":"additional","affiliation":[]},{"given":"Hua","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"Doron","family":"Nussbaum","sequence":"additional","affiliation":[]},{"given":"J\u00f6rg-R\u00fcdiger","family":"Sack","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,7,7]]},"reference":[{"issue":"6","key":"9204_CR1","doi-asserted-by":"crossref","first-page":"1689","DOI":"10.1137\/S0097539793253371","volume":"26","author":"P.K. Agarwal","year":"1997","unstructured":"Agarwal, P.K., Aronov, B., O\u2019Rourke, J., Schevon, C.A.: Star unfolding of a polytope with applications. SIAM J. Comput. 26(6), 1689\u20131713 (1997)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9204_CR2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1145\/263867.263869","volume":"44","author":"P.K. Agarwal","year":"1997","unstructured":"Agarwal, P.K., Har-Peled, S., Sharir, M., Varadarajan, K.: Approximate shortest paths on a convex polytope in three dimensions. J. ACM 44(4), 567\u2013584 (1997)","journal-title":"J. ACM"},{"issue":"2","key":"9204_CR3","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s00453-001-0111-x","volume":"33","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., Har-Peled, S., Karia, M.: Computing approximate shortest paths on convex polytopes. Algorithmica 33(2), 227\u2013242 (2002)","journal-title":"Algorithmica"},{"issue":"1","key":"9204_CR4","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1137\/S0895480194272183","volume":"9","author":"L. Aleksandrov","year":"1996","unstructured":"Aleksandrov, L., Djidjev, H.: Linear algorithms for partitioning embedded graphs of bounded genus. SIAM J. Discrete Math. 9(1), 129\u2013150 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"9204_CR5","doi-asserted-by":"crossref","unstructured":"Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.-R.: An \u03b5-approximation algorithm for weighted shortest path queries on polyhedral surfaces. In: Proc. 14th Euro CG Barcelona, pp. 19\u201321 (1998)","DOI":"10.1007\/BFb0054351"},{"key":"9204_CR6","series-title":"LNCS","first-page":"11","volume-title":"Proceedings of SWAT","author":"L. Aleksandrov","year":"1998","unstructured":"Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.-R.: An \u03b5-approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Proceedings of SWAT. LNCS, vol.\u00a01432, pp.\u00a011\u201322. Springer, Berlin (1998)"},{"key":"9204_CR7","series-title":"LNCS","first-page":"246","volume-title":"Proc. Foundations of Computation Theory","author":"L. Aleksandrov","year":"2003","unstructured":"Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.-R.: An improved approximation algorithm for computing geometric shortest paths. In: Proc. Foundations of Computation Theory. LNCS, vol.\u00a02751, pp. 246\u2013257. Springer, Berlin (2003)"},{"issue":"1","key":"9204_CR8","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"},{"key":"9204_CR9","first-page":"1.5","volume":"11","author":"L. Aleksandrov","year":"2006","unstructured":"Aleksandrov, L., Djidjev, H., Guo, H., Maheshwari, A.: Partitioning planar graphs with costs and weights. ACM J. Exp. Algorithmics 11, 1.5 (2006)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"9204_CR10","series-title":"LNCS","first-page":"98","volume-title":"Proc. 31st Int. Symp. Mathematical Foundations of Computer Science","author":"L. Aleksandrov","year":"2006","unstructured":"Aleksandrov, L., Djidjev, H., Guo, H., Maheshwari, A., Nussbaum, D., Sack, J.-R.: Approximate shortest path queries on weighted polyhedral surfaces. In: Proc. 31st Int. Symp. Mathematical Foundations of Computer Science. LNCS, vol. 4162, pp. 98\u2013109. Springer, Berlin (2006)"},{"key":"9204_CR11","series-title":"LNCS","first-page":"514","volume-title":"Proc. of the Forth Annual Fourth Annual European Symposium on Algorithms ESA\u201996","author":"S. Arikati","year":"1996","unstructured":"Arikati, S., Chen, D., Chew, L., Das, G., Smid, M., Zaroliagis, C.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proc. of the Forth Annual Fourth Annual European Symposium on Algorithms ESA\u201996. LNCS, vol.\u00a01136, pp. 514\u2013528. Springer, Berlin (1996)"},{"issue":"6","key":"9204_CR12","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1090\/S0002-9904-1962-10847-7","volume":"68","author":"J. Battle","year":"1962","unstructured":"Battle, J., Harary, F., Kodama, Y., Youngs, J.W.T.: Additivity of the genus of a graph. Bull. Am. Math. Soc. 68(6), 565\u2013568 (1962)","journal-title":"Bull. Am. Math. Soc."},{"key":"9204_CR13","doi-asserted-by":"crossref","unstructured":"Canny, J., Reif, J.H.: New lower bound techniques for robot motion planning problems. In: Proc. 28th Annu. IEEE Symposium on Foundations of Computer Sciences, pp. 49\u201360 (1987)","DOI":"10.1109\/SFCS.1987.42"},{"key":"9204_CR14","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1137\/S009753970444572X","volume":"35","author":"B. Chazelle","year":"2006","unstructured":"Chazelle, B., Liu, D., Magen, A.: Sublinear geometric algorithms. SIAM J. Comput. 35, 627\u2013646 (2006)","journal-title":"SIAM J. Comput."},{"key":"9204_CR15","unstructured":"Chen, D.: On the all-pairs Euclidean short path problem. In: Proc. 6th ACM-SIAM Sympos. on Discrete Algorithms (SODA), pp. 292\u2013301 (1995)"},{"key":"9204_CR16","series-title":"LNCS","first-page":"169","volume-title":"Proc. 1991 Int. Conf. on Comp. and Information","author":"J. Chen","year":"1991","unstructured":"Chen, J., Han, Y.: Storing shortest paths for a polyhedron. In: Proc. 1991 Int. Conf. on Comp. and Information. LNCS, vol.\u00a0497, pp. 169\u2013180. Springer, Berlin (1991)"},{"key":"9204_CR17","unstructured":"Chen, J., Han, Y.: Shortest paths on a polyhedron. In: Proceedings of 6th ACM Symposium on Computational Geometry, pp. 360\u2013369 (1990). Full version IJCGA 6, 127\u2013144 (1996)"},{"issue":"6","key":"9204_CR18","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1142\/S0218195901000675","volume":"11","author":"D.Z. Chen","year":"2001","unstructured":"Chen, D.Z., Daescu, O., Klenk, K.S.: On geometric path query problems. Int. J. Comput. Geom. Appl. 11(6), 617\u2013645 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9204_CR19","first-page":"84","volume-title":"Symposium on Computational Geometry","author":"S.-W. Cheng","year":"2007","unstructured":"Cheng, S.-W., Na, H.-S., Vigneron, A., Wang, Y.: Querying approximate shortest paths in anisotropic regions. In: Erickson, J. (ed.) Symposium on Computational Geometry, pp. 84\u201391. ACM, New York (2007)"},{"issue":"3","key":"9204_CR20","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1137\/06067777X","volume":"38","author":"S.-W. Cheng","year":"2008","unstructured":"Cheng, S.-W., Na, H.-S., Vigneron, A., Wang, Y.: Approximate shortest paths in anisotropic regions. SIAM J. Comput. 38(3), 802\u2013824 (2008)","journal-title":"SIAM J. Comput."},{"key":"9204_CR21","unstructured":"Chiang, Y.-J., Mitchell, J.: Two-point Euclidean shortest path queries in the plane. In: Proc. 10th ACM-SIAM Sympos. on Discrete Algorithms (SODA), pp. 215\u2013224 (1999)"},{"key":"9204_CR22","doi-asserted-by":"crossref","unstructured":"Clarkson, K.: Approximation algorithms for shortest path motion planing. In: Proc. 19th Annu. Symp. Theory Comput. (STOC), pp. 56\u201365 (1987)","DOI":"10.1145\/28395.28402"},{"key":"9204_CR23","series-title":"LNCS","first-page":"216","volume-title":"SWAT\u201988","author":"H.N. Djidjev","year":"1988","unstructured":"Djidjev, H.N.: Linear algorithms for graph separation problems. In: SWAT\u201988. LNCS, vol. 318, pp.\u00a0216\u2013222. Springer, Berlin (1988)"},{"issue":"1","key":"9204_CR24","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s004530010031","volume":"28","author":"H. Djidjev","year":"2000","unstructured":"Djidjev, H.: Partitioning planar graphs with vertex costs: algorithms and applications. Algorithmica 28(1), 51\u201375 (2000)","journal-title":"Algorithmica"},{"issue":"3","key":"9204_CR25","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0021-9045(74)90120-8","volume":"10","author":"R.M. Dudley","year":"1974","unstructured":"Dudley, R.M.: Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory 10(3), 227\u2013236 (1974)","journal-title":"J. Approx. Theory"},{"key":"9204_CR26","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs. SIAM J. Comput. 16, 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"key":"9204_CR27","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J.\u00a0Algorithms 5, 391\u2013407 (1984)","journal-title":"J.\u00a0Algorithms"},{"key":"9204_CR28","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"L. Guibas","year":"1989","unstructured":"Guibas, L., Hershberger, J.: Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci. 39, 126\u2013152 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9204_CR29","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/PL00009417","volume":"21","author":"S. Har-Peled","year":"1999","unstructured":"Har-Peled, S.: Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions. Discrete Comput. Geom. 21, 217\u2013231 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9204_CR30","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":"9204_CR31","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1137\/S0097539795289604","volume":"28","author":"J. Hershberger","year":"1999","unstructured":"Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28, 2215\u20132256 (1999)","journal-title":"SIAM J. Comput."},{"key":"9204_CR32","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"9204_CR33","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/102782.102784","volume":"38","author":"J. Mitchell","year":"1991","unstructured":"Mitchell, J., Papadimitriou, C.: The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM 38, 18\u201373 (1991)","journal-title":"J. ACM"},{"key":"9204_CR34","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/0216045","volume":"16","author":"J. Mitchell","year":"1987","unstructured":"Mitchell, J., Mount, D., Papadimitriou, C.: The discrete geodesic problem. SIAM J. Comput. 16, 647\u2013668 (1987)","journal-title":"SIAM J. Comput."},{"key":"9204_CR35","first-page":"191","volume-title":"Proceedings of the 4th Workshop on Algorithmic Foundations of Robotics (WAFR2000)","author":"J.H. Reif","year":"2000","unstructured":"Reif, J.H., Sun, Z.: An efficient approximation algorithm for weighted region shortest path problem. In: Proceedings of the 4th Workshop on Algorithmic Foundations of Robotics (WAFR2000), pp. 191\u2013203. AK Peters, Wellesley (2000)"},{"key":"9204_CR36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.07.004","volume":"58","author":"J.H. Reif","year":"2006","unstructured":"Reif, J.H., Sun, Z.: On finding approximate optimal paths in weighted regions. J. Algorithms 58, 1\u201332 (2006)","journal-title":"J. Algorithms"},{"key":"9204_CR37","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM 29, 669\u2013679 (1986)","journal-title":"Commun. ACM"},{"issue":"1\u20133","key":"9204_CR38","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1007\/s00454-007-9031-0","volume":"39","author":"Y. Schreiber","year":"2008","unstructured":"Schreiber, Y., Sharir, M.: An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. Discrete Comput. Geom. 39(1\u20133), 500\u2013579 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9204_CR39","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0215014","volume":"15","author":"M. Sharir","year":"1986","unstructured":"Sharir, M., Schorr, A.: On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 193\u2013215 (1986)","journal-title":"SIAM J. Comput."},{"key":"9204_CR40","series-title":"LNCS","first-page":"241","volume-title":"SIGAL International Symposium on Algorithms","author":"X. Tan","year":"1990","unstructured":"Tan, X., Hirata, T., Inagaki, Y.: Spatial point location and its applications. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds.) SIGAL International Symposium on Algorithms. LNCS, vol.\u00a0450, pp.\u00a0241\u2013250. Springer, Berlin (1990)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9204-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9204-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9204-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T18:36:01Z","timestamp":1739212561000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9204-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,7]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["9204"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9204-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2009,7,7]]}}}