{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:53:51Z","timestamp":1787320431977,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Erdos Center"},{"DOI":"10.13039\/501100010024","name":"Hungarian Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010024","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["882971"],"award-info":[{"award-number":["882971"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees (MSTs) of the original set and of the two parts. If [Formula: see text] denotes the length of an MST of [Formula: see text], we show that every set [Formula: see text] of [Formula: see text] points admits a nontrivial bipartition [Formula: see text] for which the MST-ratio [Formula: see text] is strictly larger than 1 and that 1 is the largest number with this property. Furthermore, we provide a fast algorithm that computes such a bipartition in [Formula: see text] time and one that computes the corresponding MST-ratio in [Formula: see text] time. In certain settings, a much better MST-ratio can be guaranteed. For example, if [Formula: see text] is a set of [Formula: see text] random points uniformly distributed in [Formula: see text], then for any [Formula: see text], the MST-ratio in a maximizing partition is at least [Formula: see text] with probability tending to 1 as [Formula: see text]. Our results and techniques are extendable to higher dimensions.<\/jats:p>","DOI":"10.1137\/24m1685365","type":"journal-article","created":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T08:00:27Z","timestamp":1758009627000},"page":"1883-1893","source":"Crossref","is-referenced-by-count":0,"title":["Two Trees Are Better than One"],"prefix":"10.1137","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1118-0321","authenticated-orcid":true,"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"Algoresearch, LLC, Milwaukee, WI 53217 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics, HUN-REN, Budapest, 1053 Hungary."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G\u00e9za","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics, HUN-REN, Budapest, 1053 Hungary."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,9,16]]},"reference":[{"key":"ref1","unstructured":"A. J. Ameli, F. Motiei, and M. Saghafian, On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum, preprint, https:\/\/arxiv.org\/abs\/2409.11079, 2024."},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"T. Asano, B. Bhattacharya, M. Keil, and F. Yao, Clustering algorithms based on minimum and maximum spanning trees, in Proceedings of the 4th Annual Symposium on Computational Geometry, 1988, pp. 252\u2013257.","DOI":"10.1145\/73393.73419"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.643"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90066-E"},{"key":"ref6","volume-title":"Research Problems in Discrete Geometry","author":"Brass P.","year":"2005"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/0602001"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1985.tb14564.x"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref10","unstructured":"S. C. di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, The Euclidean MST-ratio of bi-colored Lattices, preprint, in 32nd International Symposium on Graph Drawing and Network Visualization, Vol. 320, 2024."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0697065-3"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280296"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000784"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1994-1249875-4"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"ref16","first-page":"177","volume":"4","author":"Graham R. L.","year":"1976","journal-title":"Bull. Inst. Math. Acad. Sin."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(93)90257-Y"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/0402010"},{"key":"ref19","first-page":"383","volume-title":"Intuitive Geometry","author":"K\u00e9zdy A. E.","year":"1997"},{"key":"ref20","first-page":"237","volume":"1","author":"Lov\u00e1sz L.","year":"1966","journal-title":"Stud. Sci. Math. Hungar."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970029"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01181430"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21800-2"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187831"},{"key":"ref25","unstructured":"P. Valtr, Planar Point Sets with Bounded Ratios of Distances, Ph.D. thesis, Freie Universit\u00e4t, Berlin, 1994."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1951-0045403-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1685365","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:57:50Z","timestamp":1787317070000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1685365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,16]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1137\/24M1685365"],"URL":"https:\/\/doi.org\/10.1137\/24m1685365","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,16]]}}}