2026-04-17T03:52:18Zhttps://recercat.cat/oai/request

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

00925njm 22002777a 4500 dc Fernández Goycoolea, José author Hernán Herrera, Luis author Pérez Lantero, Pablo author Seara Ojea, Carlos author 2026-07-15 © 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) À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 Crossing-free monochromatic trees for bicolored point sets