{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T03:08:33Z","timestamp":1774321713912,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"NSF award","award":["CCF-2348067"],"award-info":[{"award-number":["CCF-2348067"]}]},{"name":"NSF award","award":["DMS-2154347"],"award-info":[{"award-number":["DMS-2154347"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>\n            For a set of red and blue points in the plane, a\n            <jats:italic toggle=\"yes\">Minimum Bichromatic Spanning Tree<\/jats:italic>\n            (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(n\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            time where\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is the number of points. In contrast to the standard Euclidean MST, which is always\n            <jats:italic toggle=\"yes\">plane<\/jats:italic>\n            (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings.\n          <\/jats:p>\n          <jats:p>\n            Moreover, we study the problem of finding a\n            <jats:italic toggle=\"yes\">Minimum Plane Bichromatic Spanning Tree<\/jats:italic>\n            (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al., has a ratio of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\sqrt{n})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -factor approximation algorithm for the general case.\n          <\/jats:p>","DOI":"10.1145\/3747591","type":"journal-article","created":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T14:30:57Z","timestamp":1752244257000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Plane Bichromatic Spanning Trees"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6827-2200","authenticated-orcid":false,"given":"Hugo A.","family":"Akitaya","sequence":"first","affiliation":[{"name":"University of Massachusetts Lowell, Lowell, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6396-4494","authenticated-orcid":false,"given":"Ahmad","family":"Biniaz","sequence":"additional","affiliation":[{"name":"University of Windsor, Windsor, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3803-5703","authenticated-orcid":false,"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3786-916X","authenticated-orcid":false,"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Potsdam, Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9005-6855","authenticated-orcid":false,"given":"Frederick","family":"Stock","sequence":"additional","affiliation":[{"name":"University of Massachusetts Lowell, Lowell, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"California State University Northridge, Northridge, California, USA and Tufts University, Medford, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00042-6"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.20382\/JOCG.V12I1A5"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00454-009-9143-9"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187805"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196127"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SOCG.2022.6"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-57265-8_41"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90276-N"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/S10898-022-01238-9"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCTB.2019.08.006"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2016.11.036"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215345"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1103-4"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2021.09.035"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010065"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-018-0482-X"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-017-0375-4"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00454-017-9881-Z"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-83508-8_14"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.JDA.2008.08.001"},{"issue":"3","key":"e_1_3_2_23_2","first-page":"37","article-title":"O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm","volume":"3","author":"Bor\u016fvka Otakar","year":"1926","unstructured":"Otakar Bor\u016fvka. 1926. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Praca Moravske Prirodovedecke Spolecnosti 3, 3 (1926), 37\u201358.","journal-title":"Praca Moravske Prirodovedecke Spolecnosti"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90003-G"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824782"},{"key":"e_1_3_2_26_2","volume-title":"Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG)","author":"Chan Timothy M.","year":"2011","unstructured":"Timothy M. Chan and Bryan T. Wilkinson. 2011. Bichromatic line segment intersection counting in \\({O}(n\\sqrt{\\log n})\\) time. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG). Retrieved from https:\/\/cccg.ca\/proceedings\/2011\/papers\/paper83.pdf"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2_14"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001762"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22203-0_16"},{"key":"e_1_3_2_30_2","first-page":"199","volume-title":"Proceedings of the 21st European Workshop on Computational Geometry (EwCG),","author":"Grantson Magdalene","year":"2005","unstructured":"Magdalene Grantson, Henk Meijer, and David Rappaport. 2005. Bi-chromatic minimum spanning trees. In Proceedings of the 21st European Workshop on Computational Geometry (EwCG), 199\u2013202. Retrieved from https:\/\/www.win.tue.nl\/EWCG2005\/Proceedings\/51.pdf"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01994880"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.12.005"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-013-1320-1"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.COMGEO.2007.05.006"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-46515-7_13"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55566-4_25"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13287-7_9"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-83539-1_11"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086610"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.107779"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3747591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T15:51:11Z","timestamp":1757346671000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3747591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3747591"],"URL":"https:\/\/doi.org\/10.1145\/3747591","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2025-01-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}