{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:00Z","timestamp":1740109560592,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NWO","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,3]]},"abstract":"Abstract<\/jats:title>More than 25 years ago, inspired by applications in computer graphics, Chazelle\u00a0et al. studied the following question: is it possible to cut any set of n<\/jats:italic> lines or other objects in $${\\mathbb R}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> into a subquadratic number of fragments such that the resulting fragments admit a depth order? They managed to prove an $$O(n^{9\/5})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 9<\/mml:mn>\n \/<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bound on the number of fragments, but only for the very special case of bipartite weavings of lines. Since then only little progress was made, until a breakthrough in 2016 by Aronov and Sharir, who showed that $$O(n^{3\/2}{{\\,\\mathrm{polylog}\\,}}n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n polylog<\/mml:mi>\n \n <\/mml:mrow>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> fragments suffice for any set of lines. In a follow-up paper Aronov et al. proved an $$O(n^{3\/2+\\varepsilon })$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bound for triangles, but their method uses high- (albeit constant-) degree algebraic arcs to perform the cuts. Hence, the resulting pieces have curved boundaries. Thus the following natural version of the problem is still wide open: is it possible to cut any collection of n<\/jats:italic> disjoint triangles in $${\\mathbb R}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> into a subquadratic number of triangular fragments that admit a depth order? And if so, can we compute the cuts efficiently? We answer this question by presenting an algorithm that cuts any set of n<\/jats:italic> disjoint triangles in $${\\mathbb R}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> into $$O(n^{7\/4}{{\\,\\mathrm{polylog}\\,}}n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 7<\/mml:mn>\n \/<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n polylog<\/mml:mi>\n \n <\/mml:mrow>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> triangular fragments that admit a depth order. The running time of our algorithm is $$O(n^{3.69})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3.69<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also prove a refined bound that depends on the number, K<\/jats:italic>, of intersections between the projections of the triangle edges onto the xy<\/jats:italic>-plane: we show that $$O(n^{1+\\varepsilon } + n^{1\/4} K^{3\/4}{{\\,\\mathrm{polylog}\\,}}n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n +<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n K<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n polylog<\/mml:mi>\n \n <\/mml:mrow>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> fragments suffice to obtain a depth order. This result extends to xy<\/jats:italic>-monotone surface patches bounded by a constant number of bounded-degree algebraic arcs in general position, constituting the first subquadratic bound for surface patches.<\/jats:p>","DOI":"10.1007\/s00454-019-00102-0","type":"journal-article","created":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T14:04:05Z","timestamp":1558620245000},"page":"450-469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Removing Depth-Order Cycles Among Triangles: An Algorithm Generating Triangular Fragments"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5770-3784","authenticated-orcid":false,"given":"Mark","family":"de Berg","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,23]]},"reference":[{"issue":"4","key":"102_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0925-7721(95)00005-8","volume":"5","author":"PK Agarwal","year":"1995","unstructured":"Agarwal, P.K., Katz, M.J., Sharir, M.: Computing depth orders for fat objects and related problems. Comput. Geom. 5(4), 187\u2013206 (1995)","journal-title":"Comput. Geom."},{"issue":"5","key":"102_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":"102_CR3","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Zahl, J.: An efficient algorithm for generalized polynomial partitioning and its applications. In: Proceedings of 35th International Symposium on Computational Geometry (SoCG) (2019)"},{"key":"102_CR4","unstructured":"Aronov, B., de Berg, M., Gray, C., Mumford, E.: Cutting cycles of rods in space: hardness and approximation. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908), pp. 1241\u20131248. SIAM, Philadelphia (2008)"},{"key":"102_CR5","doi-asserted-by":"crossref","unstructured":"Aronov, B., Ezra, E., Zahl, J.: Constructive polynomial partitioning for algebraic curves in $\\mathbb{R}^3$ with applications. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919), pp. 2636\u20132648. SIAM, Philadelphia (2019)","DOI":"10.1137\/1.9781611975482.163"},{"issue":"2","key":"102_CR6","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":"102_CR7","unstructured":"Aronov, B., Miller, E.Y., Sharir, M.: Eliminating depth cycles among triangles in three dimensions. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2476\u20132494 (2017). arXiv:1607.06136"},{"issue":"3","key":"102_CR8","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."},{"issue":"3","key":"102_CR9","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1137\/0213031","volume":"13","author":"B Chazelle","year":"1984","unstructured":"Chazelle, B.: Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13(3), 488\u2013507 (1984)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"102_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide and conquer. Discrete Comput. Geom. 9(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"102_CR11","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":"102_CR12","doi-asserted-by":"crossref","unstructured":"de Berg, M.: Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science, vol. 703. Springer, New York (1993)","DOI":"10.1007\/BFb0029813"},{"issue":"3","key":"102_CR13","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":"102_CR14","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":"1","key":"102_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/060672261","volume":"38","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Gray, C.: Vertical ray shooting and computing depth orders for fat objects. SIAM J. Comput. 38(1), 257\u2013275 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"102_CR16","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":"4","key":"102_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1142\/S0218195995000210","volume":"5","author":"M de Berg","year":"1995","unstructured":"de Berg, M., Schwarzkopf, O.: Cuttings and applications. Internat. J. Comput. Geom. Appl. 5(4), 343\u2013355 (1995)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"3","key":"102_CR18","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. Cambridge Phil. Soc. 159(3), 459\u2013469 (2015)","journal-title":"Math. Proc. Cambridge Phil. Soc."},{"issue":"1","key":"102_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."},{"issue":"2","key":"102_CR20","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10(2), 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"102_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."},{"issue":"1","key":"102_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0196-6774(92)90007-Y","volume":"13","author":"MS Paterson","year":"1992","unstructured":"Paterson, M.S., Yao, F.F.: Optimal binary space partitions for orthogonal objects. J. Algorithms 13(1), 99\u2013113 (1992)","journal-title":"J. Algorithms"},{"key":"102_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcta.2017.02.006","volume":"150","author":"M Sharir","year":"2017","unstructured":"Sharir, M., Zahl, J.: Cutting algebraic curves into pseudo-segments and applications. J. Comb. Theory Ser. A 150, 1\u201335 (2017)","journal-title":"J. Comb. Theory Ser. A"},{"key":"102_CR24","doi-asserted-by":"crossref","unstructured":"Solan, A.: Cutting cycles of rods in space. In: Proceedings of the 14th Annual Symposium on Computational Geometry (SCG\u201998), pp. 135\u2013142. ACM, New York (1998)","DOI":"10.1145\/276884.276899"},{"issue":"1","key":"102_CR25","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."},{"issue":"2","key":"102_CR26","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/0004-3702(94)90048-5","volume":"71","author":"RH Wilson","year":"1994","unstructured":"Wilson, R.H., Latombe, J.-C.: Geometric reasoning about mechanical assembly. Artif. Intell. 71(2), 371\u2013396 (1994)","journal-title":"Artif. Intell."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00102-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00102-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00102-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T19:56:58Z","timestamp":1612900618000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00102-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,23]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["102"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00102-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2019,5,23]]},"assertion":[{"value":"7 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}