{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:56:23Z","timestamp":1767239783735},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616801"},{"type":"electronic","value":"9783540706670"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61680-2_79","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:11:12Z","timestamp":1330294272000},"page":"514-528","source":"Crossref","is-referenced-by-count":43,"title":["Planar spanners and approximate shortest path queries among obstacles in the plane"],"prefix":"10.1007","author":[{"given":"Srinivasa","family":"Arikati","sequence":"first","affiliation":[]},{"given":"Danny Z.","family":"Chen","sequence":"additional","affiliation":[]},{"given":"L. Paul","family":"Chew","sequence":"additional","affiliation":[]},{"given":"Gautam","family":"Das","sequence":"additional","affiliation":[]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[]},{"given":"Christos D.","family":"Zaroliagis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"S. Arya, G. Das, D.M. Mount, J.S. Salowe and M. Smid, \u201cEuclidean spanners: short, thin, and lanky\u201d, Proc. 27th ACM STOC, 1995, pp. 489\u2013498.","DOI":"10.1145\/225058.225191"},{"key":"38_CR2","unstructured":"S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman and A. Wu, \u201cAn optimal algorithm for approximate nearest neighbor searching\u201d, Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, 1994, pp. 573\u2013582."},{"issue":"2","key":"38_CR3","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0925-7721(91)90002-V","volume":"1","author":"M. J. Atallah","year":"1991","unstructured":"M. J. Atallah and D. Z. Chen, \u201cParallel rectilinear shortest paths with rectangular obstacles\u201d, Comp. Geometry: Theory and Appl., 1:2 (1991), pp.79\u2013113.","journal-title":"Comp. Geometry: Theory and Appl."},{"key":"38_CR4","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0925-7721(93)90004-P","volume":"3","author":"M. J. Atallah","year":"1993","unstructured":"M. J. Atallah and D. Z. Chen, \u201cOn parallel rectilinear obstacle-avoiding paths\u201d, Computational Geometry: Theory and Applications, 3 (1993), pp. 307\u2013313.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"38_CR5","unstructured":"D. Z. Chen. \u201cOn the all-pairs Euclidean short path problem\u201d, Proc. 6th Annual ACM-SIAM Symp. on Discrete Algorithms, San Francisco, 1995, pp. 292\u2013301."},{"key":"38_CR6","unstructured":"D. Z. Chen and K. S. Klenk, \u201cRectilinear short path queries among rectangular obstacles\u201d, Proc. 7th Can. Conf. on Comp. Geometry, 1995, pp. 169\u2013174."},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"D. Z. Chen, K. S. Klenk, and H.-Y. T. Tu, \u201cRectilinear shortest path queries among weighted obstacles in the rectilinear plane\u201d, Proc. 11th Annual ACM Symp. on Computational Geometry, 1995, pp. 370\u2013379.","DOI":"10.1145\/220279.220319"},{"key":"38_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01553881","volume":"4","author":"L. P. Chew","year":"1989","unstructured":"L. P. Chew, \u201cConstrained Delaunay triangulations\u201d, Algorithmica, 4 (1989), pp. 97\u2013108.","journal-title":"Algorithmica"},{"key":"38_CR9","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"L. P. Chew","year":"1989","unstructured":"L. P. Chew, \u201cThere are planar graphs almost as good as the complete graph\u201d, J. of Computer and System Sciences, 39 (1989), pp. 205\u2013219.","journal-title":"J. of Computer and System Sciences"},{"key":"38_CR10","unstructured":"L. P. Chew, \u201cPlanar graphs and sparse graphs for efficient motion planning in the plane\u201d, Computer Science Tech Report, PCS-TR90-146, Dartmouth College."},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"L. P. Chew and R. L. Drysdale, \u201cVoronoi diagrams based on convex distance functions\u201d, Proc. 1st Annual ACM Symp. on Comp. Geometry, 1985, pp. 235\u2013244.","DOI":"10.1145\/323233.323264"},{"key":"38_CR12","unstructured":"Y.-J. Chiang, F. P. Preparata, and R. Tamassia, \u201cA unified approach to dynamic point location, ray shooting, and shortest paths in planar maps\u201d, Proc. of the 4th ACM-SIAM Symp. on Discrete Algorithms, 1993, pp. 44\u201353."},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, \u201cApproximation algorithms for shortest path motion planning\u201d, Proc. 19th Annual ACM Symp. Theory of Computing, 1987, pp. 56\u201365.","DOI":"10.1145\/28395.28402"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"H. Djidjev, G. Pantziou and C. Zaroliagis, \u201cOn-line and dynamic algorithms for shortest path problems\u201d, Proc. 12th Symp. on Theor. Aspects of Comp. Sc., LNCS 900, Springer-Verlag, 1995, pp. 193\u2013204.","DOI":"10.1007\/3-540-59042-0_73"},{"key":"38_CR15","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF02187801","volume":"5","author":"D. P. Dobkin","year":"1990","unstructured":"D. P. Dobkin, S. J. Friedman, and K. J. Supowit, \u201cDelaunay graphs are almost as good as complete graphs\u201d, Discrete & Comp. Geometry, 5 (1990), pp. 399\u2013407.","journal-title":"Discrete & Comp. Geometry"},{"issue":"1","key":"38_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1142\/S0218195994000021","volume":"4","author":"H. ElGindy","year":"1994","unstructured":"H. ElGindy and P. Mitra, \u201cOrthogonal shortest route queries among axes parallel rectangular obstacles\u201d, Int. J. of Comp. Geometry and Appl., 4 (1) (1994), 3\u201324.","journal-title":"Int. J. of Comp. Geometry and Appl."},{"key":"38_CR17","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G. Frederickson","year":"1987","unstructured":"G. Frederickson, \u201cFast algorithms for shortest paths in planar graphs, with applications\u201d, SIAM J. on Computing, 16 (1987), pp.1004\u20131022.","journal-title":"SIAM J. on Computing"},{"key":"38_CR18","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1006\/jagm.1995.1027","volume":"19","author":"G.N. Frederickson","year":"1995","unstructured":"G.N. Frederickson, \u201cUsing cellular graph embeddings in solving all pairs shortest path problems\u201d, J. of Algorithms, 19 (1995), pp. 45\u201385.","journal-title":"J. of Algorithms"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"M. Goodrich, \u201cPlanar separators and parallel polygon triangulation\u201d, Proc. 24th ACM Symp. on Theory of Comp., 1992, pp.507\u2013516.","DOI":"10.1145\/129712.129762"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich and R. Tamassia, \u201cDynamic ray shooting and shortest paths via balanced geodesic triangulations\u201d, Proc. 9th Annual ACM Symp. on Computational Geometry, 1993, pp. 318\u2013327.","DOI":"10.1145\/160985.161157"},{"key":"38_CR21","doi-asserted-by":"crossref","unstructured":"L.J. Guibas and J. Hershberger, \u201cOptimal shortest path queries in a simple polygon\u201d, Proc. 3rd Annual ACM Symp. on Computational Geometry, 1987, pp. 50\u201363.","DOI":"10.1145\/41958.41964"},{"key":"38_CR22","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L.J. Guibas","year":"1987","unstructured":"L.J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R.E. Tarjan, \u201cLinear time algorithms for visibility and shortest paths problems inside triangulated simple polygons\u201d, Algorithmica, 2 (1987), pp. 209\u2013233.","journal-title":"Algorithmica"},{"key":"38_CR23","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Rao, M. Rauch and S. Subramanian, \u201cFaster shortest-path algorithms for planar graphs\u201d, Proc. 26th ACM Symp. on Theory of Comp., 1994, pp.27\u201337.","DOI":"10.1145\/195058.195092"},{"key":"38_CR24","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. Lipton","year":"1979","unstructured":"R. Lipton and R. Tarjan, \u201cA separator theorem for planar graphs\u201d, SIAM J. Applied Mathematics, 36 (1979), pp.177\u2013189.","journal-title":"SIAM J. Applied Mathematics"},{"issue":"6","key":"38_CR25","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin, \u201cOn finding lowest common ancestors: Simplification and parallelization\u201d, SIAM J. Computing, 17:6 (1988), pp.1253\u20131262.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61680-2_79.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:09:16Z","timestamp":1605647356000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61680-2_79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616801","9783540706670"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-61680-2_79","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}