2026-04-17T01:02:44Zhttps://recercat.cat/oai/request
oai:recercat.cat:2117/4601512026-04-08T10:43:51Zcom_2072_1033col_2072_452950
RECERCAT author Fernández Goycoolea, José author Hernán Herrera, Luis author Pérez Lantero, Pablo author Seara Ojea, Carlos 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 ReviewedPostprint (author's final draft) http://creativecommons.org/licenses/by-nc-nd/4.0/ Restricted access - publisher's policy Attribution-NonCommercial-NoDerivatives 4.0 International À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 Article