{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:02Z","timestamp":1725664082236},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_1","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:37:06Z","timestamp":1330270626000},"page":"1-12","source":"Crossref","is-referenced-by-count":5,"title":["Computing depth orders and related problems"],"prefix":"10.1007","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0219020","volume":"19","author":"P. K. Agarwal","year":"1990","unstructured":"P.K. Agarwal and M. Sharir, Red-blue intersection detection algorithms, with applications to motion planning and collision detection, SIAM J. Computing 19 (1990), 297\u2013321.","journal-title":"SIAM J. Computing"},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/BF01758853","volume":"8","author":"H. Alt","year":"1992","unstructured":"H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. N\u00e4her, S. Schirra and C. Uhrig, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, Algorithmica 8 (1992), 391\u2013406.","journal-title":"Algorithmica"},{"key":"1_CR3","unstructured":"B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir and J. Snoeyink, Ray shooting in polygons using geodesic triangulations, to appear in Algorithmica."},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry, Discrete Comput. Geom. 4 (1989), 551\u2013581.","journal-title":"Discrete Comput. Geom."},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"M. de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Lecture Notes in Computer Science, vol. 703, Springer-Verlag, 1993.","DOI":"10.1007\/BFb0029813"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"M. de Berg, D. Halperin, M.H. Overmars, J. Snoeyink and M. van Kreveld, Efficient ray shooting and hidden surface removal, Proc. 7th ACM Symp, on Computational Geometry, 1991, 21\u201330.","DOI":"10.1145\/109648.109651"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1137\/S0097539791223747","volume":"23","author":"M. Berg de","year":"1994","unstructured":"M. de Berg, M. Overmars and O. Schwarzkopf, Computing and verifying depth orders, SIAM J. Computing 23 (1994), 437\u2013446.","journal-title":"SIAM J. Computing"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0925-7721(93)90018-2","volume":"3","author":"A. Efrat","year":"1993","unstructured":"A. Efrat, G. Rote and M. Sharir, On the union of fat wedges and separating a collection of segments by a line, Comp. Geom. Theory and Appls 3 (1993), 277\u2013288.","journal-title":"Comp. Geom. Theory and Appls"},{"issue":"2","key":"1_CR9","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica 6 (2) (1986), 151\u2013177.","journal-title":"Combinatorica"},{"key":"1_CR10","unstructured":"D. Hearn and M.P. Baker, Computer Graphics, Prentice-Hall International, 1986."},{"key":"1_CR11","unstructured":"J. Hershberger and S. Suri, A pedestrian approach to ray shooting: Shoot a ray, take a walk, Proc. 4th ACM-SIAM Symp. Discrete Algorithms, 1993, 54\u201363."},{"key":"1_CR12","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0925-7721(92)90024-M","volume":"2","author":"M. J. Katz","year":"1992","unstructured":"M.J. Katz, M.H. Overmars, M. Sharir, Efficient hidden surface removal for objects with small union size, Comp. Geom. Theory and Appls 2 (1992), 223\u2013234.","journal-title":"Comp. Geom. Theory and Appls"},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1137\/S009753979018330X","volume":"23","author":"J. Matou\u0161ek","year":"1994","unstructured":"J. Matou\u0161ek, J. Pach, M. Sharir, S. Sifrony and E. Welzl, Fat triangles determine linearly many holes, SIAM J. Computing 23 (1994), 154\u2013169.","journal-title":"SIAM J. Computing"},{"key":"1_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69900-9","volume-title":"Data Structures and Algorithms 3: Multidimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn, Data Structures and Algorithms 3: Multidimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984."},{"key":"1_CR15","unstructured":"N. Miller and M. Sharir, Efficient randomized algorithms for constructing the union of fat triangles and of pseudodiscs, manuscript, 1991."},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"M. van Kreveld, On fat partitioning, fat covering, and the union size of polygons, Proc. 3rd Workshop on Algorithms and Data Structures, 1993, 452\u2013463.","DOI":"10.1007\/3-540-57155-8_270"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:12:57Z","timestamp":1619572377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}