{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:03:38Z","timestamp":1710349418337},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1990,6,1]],"date-time":"1990-06-01T00:00:00Z","timestamp":644198400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1990,6]]},"DOI":"10.1007\/bf02187791","type":"journal-article","created":{"date-parts":[[2005,9,20]],"date-time":"2005-09-20T18:17:21Z","timestamp":1127240241000},"page":"289-304","source":"Crossref","is-referenced-by-count":20,"title":["Computing simple circuits from a set of line segments"],"prefix":"10.1007","volume":"5","author":[{"given":"David","family":"Rappaport","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Imai","sequence":"additional","affiliation":[]},{"given":"Godfried T.","family":"Toussaint","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1990,6,1]]},"reference":[{"key":"BF02187791_CR1","first-page":"13","volume-title":"Computational Morphology","author":"D. Avis","year":"1988","unstructured":"D. Avis and D. Rappaport, Computing monotone simple circuits in the plane, inComputational Morphology (G. Toussaint, ed.), 13\u201323, North-Holland, Amsterdam (1988)."},{"issue":"9","key":"BF02187791_CR2","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. A. Ottmann, Algorithms for reporting and counting geometric intersections,IEEE Trans. Comput. 28, 9 (1979), 643\u2013647.","journal-title":"IEEE Trans. Comput."},{"key":"BF02187791_CR3","doi-asserted-by":"crossref","unstructured":"N. Friedman, Some results on the effect of arithmetics on comparison problems,Proc. 13th IEEE Symp. Switching Automata Theory (1972), 139\u2013142.","DOI":"10.1109\/SWAT.1972.24"},{"key":"BF02187791_CR4","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and R. E. Tarjan, The planar Hamiltonian circuit problem is NP-complete,SIAM J. Comput. 5 (1976), 704\u2013714.","journal-title":"SIAM J. Comput."},{"key":"BF02187791_CR5","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set,Inform. Process. Lett. 1 (1972), 132\u2013133.","journal-title":"Inform. Process. Lett."},{"key":"BF02187791_CR6","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft and R. M. Karp, Ann 5\/2 algorithm for maximum matchings in bipartite graphs,SIAM J. Comput. 2 (1973), 225\u2013231.","journal-title":"SIAM J. Comput."},{"key":"BF02187791_CR7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R. M. Karp","year":"1975","unstructured":"R. M. Karp, On the complexity of combinatorial problems,Networks 5 (1975), 45\u201368.","journal-title":"Networks"},{"key":"BF02187791_CR8","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. Kirkpatrick","year":"1986","unstructured":"D. Kirkpatrick and R. Seidel, The ultimate convex hull algorithm,SIAM J. Comput. 15 (1986), 287\u2013299.","journal-title":"SIAM J. Comput."},{"key":"BF02187791_CR9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0167-8655(85)90039-X","volume":"3","author":"M. McQueen","year":"1985","unstructured":"M. McQueen and G. T. Toussaint, On the ultimate convex hull algorithm in practice,Pattern Recognition Lett. 3 (1985), 29\u201334.","journal-title":"Pattern Recognition Lett."},{"key":"BF02187791_CR10","unstructured":"D. Rappaport, The Complexity of Computing Simple Circuits in the Plane, Ph.D. thesis, McGill University (1986)."},{"key":"BF02187791_CR11","doi-asserted-by":"crossref","unstructured":"D. Rappaport, Computing simple circuits from a set of line segments is NP-complete,Proc. 3rd ACM Symp. Comput. Geom. (1987), 322\u2013330.","DOI":"10.1145\/41958.41993"},{"key":"BF02187791_CR12","doi-asserted-by":"crossref","unstructured":"M. I. Shamos, Geometric complexity,Proc. 7th ACM Annu. Symp. Theory Comput. (1975), 224\u2013233.","DOI":"10.1145\/800116.803772"},{"key":"BF02187791_CR13","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey, Geometric intersection problems,Proc. 17th IEEE Annu. Symp. Found. Comput. Sci. (1976), 208\u2013215.","DOI":"10.1109\/SFCS.1976.16"},{"key":"BF02187791_CR14","unstructured":"S. Suri, Personal communication (1986)."},{"key":"BF02187791_CR15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R. E. Tarjan","year":"1988","unstructured":"R. E. Tarjan and C. Van Wyk, AnO(n log logn) algorithm for triangulating a simple polygon,SIAM J. Comput. 17 (1988), 143\u2013178.","journal-title":"SIAM J. Comput."},{"key":"BF02187791_CR16","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0167-8655(85)90038-8","volume":"3","author":"G. T. Toussaint","year":"1985","unstructured":"G. T. Toussaint, A historical note on convex hull finding algorithms,Pattern Recognition Lett. 3 (1985), 21\u201328.","journal-title":"Pattern Recognition Lett."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187791.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187791\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T17:22:35Z","timestamp":1557854555000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["BF02187791"],"URL":"https:\/\/doi.org\/10.1007\/bf02187791","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}