2026-04-17T06:17:19Zhttps://recercat.cat/oai/request

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

urn:hdl:2117/460151 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 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 Elsevier