{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:13:29Z","timestamp":1769076809073,"version":"3.49.0"},"reference-count":23,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1992,12,1]],"date-time":"1992-12-01T00:00:00Z","timestamp":723168000000},"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":7533,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1992,12]]},"DOI":"10.1016\/0304-3975(92)90252-b","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:47:37Z","timestamp":1027640857000},"page":"265-281","source":"Crossref","is-referenced-by-count":13,"title":["Fast geometric approximation techniques and geometric embedding problems"],"prefix":"10.1016","volume":"106","author":[{"given":"Marshall W.","family":"Bern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Howard J.","family":"Karloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(92)90252-B_BIB1","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/SFCS.1988.21937","article-title":"Parallel comparison algorithms for approximation problems","author":"Alon","year":"1988","journal-title":"Proc. 29th IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(92)90252-B_BIB2","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1145\/358315.358392","article-title":"Approximation algorithms for convex hulls","volume":"25","author":"Bentley","year":"1982","journal-title":"CACM"},{"key":"10.1016\/0304-3975(92)90252-B_BIB3","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/BF02779671","article-title":"Graphs whose every transitive orientation contains almost every relation","volume":"59","author":"Bollob\u00e1s","year":"1987","journal-title":"Israel J. Math."},{"key":"10.1016\/0304-3975(92)90252-B_BIB4","author":"Chew","year":"1988","journal-title":"There are planar graphs almost as good as the complete graph"},{"key":"10.1016\/0304-3975(92)90252-B_BIB5","article-title":"Sorting helps for Voronoi diagrams","author":"Chew","year":"1988","journal-title":"13th Symp. on Mathematical Programming"},{"key":"10.1016\/0304-3975(92)90252-B_BIB6","series-title":"Symp. on Algorithms and Complexity","article-title":"Worst-case analysis of a new heuristic for the traveling salesman problem","author":"Christofides","year":"1976"},{"key":"10.1016\/0304-3975(92)90252-B_BIB7","author":"Chrobak","year":"1989","journal-title":"UC-Riverside"},{"key":"10.1016\/0304-3975(92)90252-B_BIB8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0898-1221(84)90085-3","article-title":"On linear arrangements of trees","volume":"10","author":"Chung","year":"1984","journal-title":"Comput. Math. Appl."},{"key":"10.1016\/0304-3975(92)90252-B_BIB9","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(92)90252-B_BIB10","first-page":"10","article-title":"Some NP-complete geometric problems","author":"Garey","year":"1976","journal-title":"Proc. 8th ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(92)90252-B_BIB11","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/0304-3975(92)90252-B_BIB12","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1109\/SFCS.1989.63542","article-title":"Approximation algorithms for minimum cost embeddings of graphs in the plane","author":"Hansen","year":"1989","journal-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(92)90252-B_BIB13","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","article-title":"Upper bounds for sorting integers on random access machines","volume":"28","author":"Kirkpatrick","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90252-B_BIB14","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1109\/TC.1985.1676584","article-title":"Wafer-scale integration of systolic arrays","volume":"C-34","author":"Leighton","year":"1985","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(92)90252-B_BIB15","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","article-title":"The complexity of restricted spanning tree problems","volume":"29","author":"Papadimitriou","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(92)90252-B_BIB16","series-title":"Computational Geometry: An Introduction","author":"Preparata","year":"1985"},{"key":"10.1016\/0304-3975(92)90252-B_BIB17","article-title":"Graph Embeddings 1988: recent breakthroughs, new directions","author":"Rosenberg","year":"1988","journal-title":"Aegean Workshop on Computing"},{"key":"10.1016\/0304-3975(92)90252-B_BIB18","series-title":"Algorithms","author":"Sedgewick","year":"1988"},{"key":"10.1016\/0304-3975(92)90252-B_BIB19","first-page":"268","article-title":"Lower bounds from complex function theory","author":"Shamos","year":"1976","journal-title":"Proc. 17th IEEE Symp. on Foundations of Computer Science"},{"key":"10.1016\/0304-3975(92)90252-B_BIB20","first-page":"422","article-title":"Geometry helps in matching","author":"Vaidya","year":"1988","journal-title":"Proc. 20th ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(92)90252-B_BIB21","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1137\/0217035","article-title":"Minimum spanning trees in k-dimensional space","volume":"17","author":"Vaidya","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(92)90252-B_BIB22","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/BF01553909","article-title":"Approximate minimum weight matching on points in k-dimensional space","volume":"4","author":"Vaidya","year":"1989","journal-title":"Algorithmica"},{"key":"10.1016\/0304-3975(92)90252-B_BIB23","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","article-title":"Design and implementation of an efficient priority queue","volume":"10","author":"van Emde Boas","year":"1977","journal-title":"Math. Systems Theory"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290252B?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290252B?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T06:20:28Z","timestamp":1580883628000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759290252B"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,12]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,12]]}},"alternative-id":["030439759290252B"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(92)90252-b","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1992,12]]}}}