{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:06:57Z","timestamp":1766135217398},"reference-count":16,"publisher":"Elsevier BV","issue":"2-3","license":[{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4429,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2001,6]]},"DOI":"10.1016\/s0166-218x(00)00280-8","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T21:59:10Z","timestamp":1027634350000},"page":"151-167","source":"Crossref","is-referenced-by-count":16,"title":["Lower bounds for computing geometric spanners and approximate shortest paths"],"prefix":"10.1016","volume":"110","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gautam","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(00)00280-8_BIB1","doi-asserted-by":"crossref","unstructured":"S. Arikati, D.Z. Chen, L.P. Chew, G. Das, M. Smid, C.D. Zaroliagis, Planar spanners and approximate shortest path queries among obstacles in the plane, Proceedings fourth Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, Vol. 1136, Springer, Berlin, 1996, pp. 514\u2013528.","DOI":"10.1007\/3-540-61680-2_79"},{"key":"10.1016\/S0166-218X(00)00280-8_BIB2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Lower bounds for algebraic computation trees, Proceedings 15th Annual ACM Symposium on the Theory of Computing, 1983, pp. 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"10.1016\/S0166-218X(00)00280-8_BIB3","unstructured":"P.B. Callahan, S.R. Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings fourth Annual Symposium on Discrete Algorithms, 1993, pp. 291\u2013300."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01553881","article-title":"Constrained Delaunay triangulations","volume":"4","author":"Chew","year":"1989","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(00)00280-8_BIB5","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","article-title":"There are planar graphs almost as good as the complete graph","volume":"39","author":"Chew","year":"1989","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB6","unstructured":"L.P. Chew, Planar graphs and sparse graphs for efficient motion planning in the plane, Computer Science Technical Report, PCS-TR90-146, Dartmouth College."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB7","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings 19th Annual ACM Symposium on the Theory of Computing, 1987, pp. 56\u201365.","DOI":"10.1145\/28395.28402"},{"key":"10.1016\/S0166-218X(00)00280-8_BIB8","unstructured":"G. Das, The visibility graph contains a bounded-degree spanner, Proceedings ninth Canadian Conference on Computational Geometry, 1997, pp. 70\u201375."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB9","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1137\/S0097539795289604","article-title":"An optimal algorithm for Euclidean shortest paths in the plane","volume":"28","author":"Hershberger","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB10","unstructured":"J.S.B. Mitchell, An optimal algorithm for shortest rectilinear paths among obstacles, Proceedings 1st Canadian Conference on Computational Geometry, 1989, p. 22."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01758836","article-title":"L1 shortest paths among polygonal obstacle in the plane","volume":"8","author":"Mitchell","year":"1992","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(00)00280-8_BIB12","series-title":"Computational Geometry, an Introduction","author":"Preparata","year":"1985"},{"key":"10.1016\/S0166-218X(00)00280-8_BIB13","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02187714","article-title":"Rectilinear shortest paths in the presence of rectangular barriers","volume":"4","author":"de Rezende","year":"1989","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB14","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1142\/S0218195991000098","article-title":"Constructing multidimensional spanner graphs","volume":"1","author":"Salowe","year":"1991","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB15","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02574695","article-title":"A sparse graph almost as good as the complete graph on points in K dimensions","volume":"6","author":"Vaidya","year":"1991","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0166-218X(00)00280-8_BIB16","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1137\/0220041","article-title":"Lower bounds for algebraic computation trees with integer inputs","volume":"20","author":"Yao","year":"1991","journal-title":"SIAM J. Comput."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002808?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002808?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T18:50:11Z","timestamp":1555699811000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X00002808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,6]]},"references-count":16,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2001,6]]}},"alternative-id":["S0166218X00002808"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(00)00280-8","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2001,6]]}}}