{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:47Z","timestamp":1725664187700},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540583257"},{"type":"electronic","value":"9783540486534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58325-4_162","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:44:30Z","timestamp":1330271070000},"page":"20-28","source":"Crossref","is-referenced-by-count":0,"title":["Every set of disjoint line segments admits a binary tree"],"prefix":"10.1007","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Michael E.","family":"Houle","sequence":"additional","affiliation":[]},{"given":"Godfried","family":"Toussaint","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"4_CR1","volume-title":"Computational Morphology","author":"D. Avis","year":"1988","unstructured":"D. Avis and D. Rappaport. Computing monotone simple circuits in the plane. Computational Morphology. Elsevier Science, G.T. Toussaint (editor), North Holland, 1988."},{"key":"4_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. A. Bondy","year":"1976","unstructured":"J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Elsevier Science, New York, New York, 1976."},{"key":"4_CR3","first-page":"91","volume":"1","author":"P. Bose","year":"1993","unstructured":"P. Bose and G. Toussaint. Growing a tree from its branches, Proc. of the First Pacific Conference on Computer Graphics and Applications, Vol 1, pp. 91\u2013103, 1993, Also: McGill Technical Report no. SOCS 92.12, McGill University, 1992.","journal-title":"Proc. of the First Pacific Conference on Computer Graphics and Applications"},{"key":"4_CR4","unstructured":"P. Bose, M. Houle, and G. Toussaint. Every set of line segments admits a binary tree. McGill Technical Report, McGill University, (to appear)."},{"issue":"1","key":"4_CR5","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0925-7721(92)90018-N","volume":"2","author":"A. Mirzaian","year":"1992","unstructured":"A. Mirzaian. Hamiltonian Triangulations and Circumscribing Polygons of Disjoint Line Segments. Computational Geometry: Theory and Applications, 2, 1, pp. 15\u201330, 1992.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"C. Monma and S. Suri. Transitions in geometric minimum spanning trees. Proc. ACM Symp. on Comp. Geom., pp. 239\u2013249, 1991.","DOI":"10.1145\/109648.109675"},{"key":"4_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. Preparata","year":"1985","unstructured":"F. Preparata and M. Shamos. Computational Geometry: An Introduction, Springer-Verlag, New York, New York, 1985."},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"D. Rappaport. Computing simple circuits from a set of line segments is NP-complete. Proc. 3rd ACM Symposium on Computational Geometry, Waterloo, Ontario, pp. 52\u201360, 1987.","DOI":"10.1145\/41958.41993"},{"issue":"3","key":"4_CR9","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF02187791","volume":"5","author":"D. Rappaport","year":"1990","unstructured":"D. Rappaport, H. Imai, and G.T. Toussaint. Computing simple circuits from a set of line segments. Discrete and Computational Geometry, 5, 3, pp. 289\u2013304, 1990.","journal-title":"Discrete and Computational Geometry"},{"key":"4_CR10","unstructured":"E. Rivera-Campo and J. Urrutia. Personal communication. August 1992."},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0190(87)90038-X","volume":"26","author":"X. Shen","year":"1987","unstructured":"X. Shen and H. Edelsbrunner. A tight lower bound on the size of visibility graphs, Information Processing Letters, 26, pp. 61\u201364, 1987.","journal-title":"Information Processing Letters"},{"issue":"1","key":"4_CR12","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0925-7721(92)90020-S","volume":"2","author":"M. Urabe","year":"1992","unstructured":"M. Urabe and M. Watanabe. On a counterexample to a conjecture of Mirzaian. Computational Geometry: Theory and Applications, 2, 1, pp. 51\u201353, 1992.","journal-title":"Computational Geometry: Theory and Applications"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58325-4_162.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:19:24Z","timestamp":1605647964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58325-4_162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540583257","9783540486534"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-58325-4_162","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}