2026-04-14T02:34:32Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/4601512026-04-08T10:43:51Zcom_2072_1033col_2072_452950

Crossing-free monochromatic trees for bicolored point sets Fernández Goycoolea, José Hernán Herrera, Luis Pérez Lantero, Pablo Seara Ojea, Carlos Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria convexa i discreta Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat Colored points in the plane Non-intersecting trees Monochromatic trees © 2026 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ We study the problem of connecting the points of a bicolored point set S = R U B by monochromatic non-overlapping geometric trees. As has been done for similar geometric problems, we characterize the minimum number of trees required in terms of the number t of non-monochromatic edges in the convex hull. Then, we propose an algorithm to construct this forest aiming to maintain the trees’ diameter long. The algorithm constructs two non-overlapping caterpillar trees when t <= 2, and a forest of trees composed of linked caterpillars if t > 2. Moreover, a process to flatten such caterpillars into paths when possible is discussed and exemplified. A qualitative comparison with an existing algorithm is also presented. Supported by project DICYT 042332PL, Vicerrector´ıa de Investigaci´on, Desarrollo e Innovaci´on USACH (Chile). Supported by grant PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. Peer Reviewed Postprint (author's final draft) 2026-07-15 Article Fernández, J. [et al.]. Crossing-free monochromatic trees for bicolored point sets. «Discrete applied mathematics», 15 Juliol 2026, vol. 387, p. 260-271. 1872-6771 https://hdl.handle.net/2117/460151 10.1016/j.dam.2026.02.049 eng https://www.sciencedirect.com/science/article/abs/pii/S0166218X26001277 info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/PID2023-150725NB-I00/ES/GRAFOS GEOMETRICOS Y ABSTRACTOS: TEORIA Y APLICACIONES/ http://creativecommons.org/licenses/by-nc-nd/4.0/ Restricted access - publisher's policy Attribution-NonCommercial-NoDerivatives 4.0 International 12 p. application/pdf Elsevier