{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:14Z","timestamp":1740109574370,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T00:00:00Z","timestamp":1594684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T00:00:00Z","timestamp":1594684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00454-020-00221-z","type":"journal-article","created":{"date-parts":[[2020,7,14]],"date-time":"2020-07-14T17:03:46Z","timestamp":1594746226000},"page":"627-653","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Eliminating Depth Cycles Among Triangles in Three Dimensions"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3110-4702","authenticated-orcid":false,"given":"Boris","family":"Aronov","sequence":"first","affiliation":[]},{"given":"Edward Y.","family":"Miller","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2541-3763","authenticated-orcid":false,"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,14]]},"reference":[{"key":"221_CR1","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Zahl, J.: An efficient algorithm for generalized polynomial partitioning and its applications. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol.\u00a0129, #\u00a05. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"5","key":"221_CR2","doi-asserted-by":"publisher","first-page":"1422","DOI":"10.1137\/S0097539797320578","volume":"29","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Grove, E.F., Murali, T.M., Vitter, J.S.: Binary space partitions for fat rectangles. SIAM J. Comput. 29(5), 1422\u20131448 (2000)","journal-title":"SIAM J. Comput."},{"key":"221_CR3","unstructured":"Aronov, B., de Berg, M., Gray, C., Mumford, E.: Cutting cycles of rods in space: hardness and approximation. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1241\u20131248. ACM, New York (2008)"},{"key":"221_CR4","doi-asserted-by":"crossref","unstructured":"Aronov, B., Ezra, E., Zahl, J.: Constructive polynomial partitioning for algebraic curves in $${\\mathbb{R}}^3$$ with applications. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2636\u20132648. SIAM, Philadelphia (2019). Updated version at arXiv:1904.09526","DOI":"10.1137\/1.9781611975482.163"},{"issue":"2","key":"221_CR5","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s00454-004-1123-5","volume":"33","author":"B Aronov","year":"2005","unstructured":"Aronov, B., Koltun, V., Sharir, M.: Cutting triangular cycles of lines in space. Discrete Comput. Geom. 33(2), 231\u2013247 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"221_CR6","doi-asserted-by":"crossref","unstructured":"Aronov, B., Miller, E.Y., Sharir, M.: Eliminating depth cycles among triangles in three dimensions. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2476\u20132494. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.164"},{"issue":"3","key":"221_CR7","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1007\/s00454-017-9920-9","volume":"59","author":"B Aronov","year":"2018","unstructured":"Aronov, B., Sharir, M.: Almost tight bounds for eliminating depth cycles in three dimensions. Discrete Comput. Geom. 59(3), 725\u2013741 (2018)","journal-title":"Discrete Comput. Geom."},{"key":"221_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029813","volume-title":"Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science","author":"M de Berg","year":"1993","unstructured":"de Berg, M.: Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science, vol. 703. Springer, Berlin (1993)"},{"issue":"3","key":"221_CR9","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s004530010047","volume":"28","author":"M de Berg","year":"2000","unstructured":"de Berg, M.: Linear size binary space partitions for uncluttered scenes. Algorithmica 28(3), 353\u2013366 (2000)","journal-title":"Algorithmica"},{"key":"221_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00102-0","author":"M de Berg","year":"2019","unstructured":"de Berg, M.: Removing depth-order cycles among triangles: an algorithm generating triangular fragments. Discrete Comput. Geom. (2019). https:\/\/doi.org\/10.1007\/s00454-019-00102-0","journal-title":"Discrete Comput. Geom."},{"key":"221_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry. Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)"},{"issue":"2","key":"221_CR12","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0097539791223747","volume":"23","author":"M de Berg","year":"1994","unstructured":"de Berg, M., Overmars, M., Schwarzkopf, O.: Computing and verifying depth orders. SIAM J. Comput. 23(2), 437\u2013446 (1994)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"221_CR13","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0925-7721(92)90009-H","volume":"1","author":"B Chazelle","year":"1992","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Pollack, R., Seidel, R., Sharir, M., Snoeyink, J.: Counting and cutting cycles of lines and rods in space. Comput. Geom. 1(6), 305\u2013323 (1992)","journal-title":"Comput. Geom."},{"key":"221_CR14","volume-title":"Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics","author":"D Cox","year":"2007","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (2007)"},{"key":"221_CR15","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., T\u00f3th, C.D.: Binary space partitions. In: Encyclopedia of Algorithms, pp. 220\u2013223. Springer, Boston (2016)","DOI":"10.1007\/978-1-4939-2864-4_511"},{"key":"221_CR16","volume-title":"Introduction to Intersection Theory in Algebraic Geometry. CBMS Regional Conference Series in Mathematics","author":"W Fulton","year":"1984","unstructured":"Fulton, W.: Introduction to Intersection Theory in Algebraic Geometry. CBMS Regional Conference Series in Mathematics, vol. 54. American Mathematical Society, Providence (1984)"},{"issue":"3","key":"221_CR17","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1017\/S0305004115000468","volume":"159","author":"L Guth","year":"2015","unstructured":"Guth, L.: Polynomial partitioning for a set of varieties. Math. Proc. Camb. Philos. Soc. 159(3), 459\u2013469 (2015)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"1","key":"221_CR18","doi-asserted-by":"publisher","first-page":"155","DOI":"10.4007\/annals.2015.181.1.2","volume":"181","author":"L Guth","year":"2015","unstructured":"Guth, L., Katz, N.H.: On the Erd\u0151s distinct distances problem in the plane. Ann. Math. 181(1), 155\u2013190 (2015)","journal-title":"Ann. Math."},{"issue":"1","key":"221_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00454-001-0026-y","volume":"26","author":"S Har-Peled","year":"2001","unstructured":"Har-Peled, S., Sharir, M.: Online point location in planar arrangements and its applications. Discrete Comput. Geom. 26(1), 19\u201340 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"221_CR20","volume-title":"Algebraic Geometry. A First Course. Graduate Texts in Mathematics","author":"J Harris","year":"1992","unstructured":"Harris, J.: Algebraic Geometry. A First Course. Graduate Texts in Mathematics, vol. 133. Springer, New York (1992)"},{"issue":"5","key":"221_CR21","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02187806","volume":"5","author":"MS Paterson","year":"1990","unstructured":"Paterson, M.S., Yao, F.F.: Efficient binary space partitions for hidden-surface removal and solid modeling. Discrete Comput. Geom. 5(5), 485\u2013503 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"221_CR22","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"key":"221_CR23","doi-asserted-by":"crossref","unstructured":"Solan, A.: Cutting cycles of rods in space. In: 14th Annual ACM Symposium on Computational Geometry, pp. 135\u2013142. ACM, New York (1998)","DOI":"10.1145\/276884.276899"},{"key":"221_CR24","volume-title":"Algebraic Topology","author":"EH Spanier","year":"1966","unstructured":"Spanier, E.H.: Algebraic Topology. McGraw-Hill, New York (1966)"},{"key":"221_CR25","unstructured":"T\u00f3th, C.D.: Binary space partitions: recent developments. In: Combinatorial and Computational Geometry. Mathematical Sciences Research Institute Publications, vol. 52, pp. 529\u2013556. Cambridge University Press, Cambridge (2005)"},{"issue":"1","key":"221_CR26","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1137\/06065934X","volume":"38","author":"CD T\u00f3th","year":"2008","unstructured":"T\u00f3th, C.D.: Binary space partitions for axis-aligned fat rectangles. SIAM J. Comput. 38(1), 429\u2013447 (2008)","journal-title":"SIAM J. Comput."},{"key":"221_CR27","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","volume":"133","author":"HE Warren","year":"1968","unstructured":"Warren, H.E.: Lower bounds for approximation by nonlinear manifolds. Trans. Am. Math. Soc. 133, 167\u2013178 (1968)","journal-title":"Trans. Am. Math. Soc."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00221-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00221-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00221-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T23:46:17Z","timestamp":1626219977000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00221-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,14]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["221"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00221-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,7,14]]},"assertion":[{"value":"7 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}