{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:43Z","timestamp":1725663523403},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540180883"},{"type":"electronic","value":"9783540477471"}],"license":[{"start":{"date-parts":[[1987,1,1]],"date-time":"1987-01-01T00:00:00Z","timestamp":536457600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18088-5_32","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:26:21Z","timestamp":1330179981000},"page":"376-385","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Nearly optimal heuristics for binary search trees with geometric generalizations"],"prefix":"10.1007","author":[{"given":"Christos","family":"Levcopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg-R.","family":"Sack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"T.C. Hu and A.C. Tucker, Optimal Computer Search Trees and Variable-Length Alpha-betical Codes, SIAM J. Applied Math. 21, pp. 514\u2013532.","DOI":"10.1137\/0121057"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"A.M. Garsia and M.L. Wachs, A new algorithm for minimum cost binary trees, SICOMP 4, 622\u2013642.","DOI":"10.1137\/0206045"},{"key":"32_CR3","unstructured":"P.D. Gilbert, New Results in Planar Triangulations, M.S. Thesis, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois."},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"L. Gotlieb, Optimal Multi-way Search Trees, SIAM J. Comput. vol. 10, No. 3","DOI":"10.1137\/0210031"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"G.T. Klincsek, Minimal triangulations of polygonal domains, Ann. Discrete Math., vol. 9, pp. 121\u2013123.","DOI":"10.1016\/S0167-5060(08)70044-X"},{"key":"32_CR6","unstructured":"D.E. Knuth, The Art of Computer Programming 3: Sorting and Searching, Addison-Wesley, Reading Massachusetts."},{"key":"32_CR7","unstructured":"C. Levcopoulos, New Results about the Approximation Behavior of the Greedy Triangulation, Link\u00f6ping Studies in Science and Technology, Thesis No 74."},{"key":"32_CR8","unstructured":"C. Levcopoulos, New Heuristics for Constructing Optimal Search Trees (in preparation)."},{"key":"32_CR9","unstructured":"A. Lingas, The Greedy Triangulation Heuristic for Minimum Weight Triangulation of Convex Polygons Approximates the Optimum, research report, LITH-IDA-R86-11, Link\u00f6ping University."},{"key":"32_CR10","unstructured":"C. Levcopoulos and A. Lingas, On Approximation Behavior of the Greedy Triangulation for Convex Polygons, to appear in Algorithmica."},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos, A. Lingas and J. Sack, Nearly Optimal Heuristics for Binary Search Trees and their Geometric Generalizations, technical report, Link\u00f6ping University, 1987.","DOI":"10.1007\/3-540-18088-5_32"},{"key":"32_CR12","unstructured":"A. Lingas, C. Levcopoulos and J. Sack, Optimal Algorithms for Minimum Length Partitions of Polygons, submitted to BIT."},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"D.T. Lee and F.P. Preparata, The all nearest neighbor problem for convex polygons, Information Processing Letters, vol. 7, no. 4, pp. 189\u2013192.","DOI":"10.1016\/0020-0190(78)90066-2"},{"key":"32_CR14","unstructured":"K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Spring. Verlag, Heidelberg."},{"key":"32_CR15","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry, An Introduction, Texts and Monographs in Computer Science, Spring. Verlag, New York."},{"key":"32_CR16","unstructured":"D.D. Sleator, R.E. Tarjan and W.P. Thurston, Rotation Distance, Triangulations, and Hyperbolic Geometry, Proc. of the 18th ACM Symposium on Theory of Computing, Berkley, California."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18088-5_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:02:21Z","timestamp":1578517341000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18088-5_32"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540180883","9783540477471"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-18088-5_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]},"assertion":[{"value":"29 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}