Crossing-free monochromatic trees for bicolored point sets

Abstract

© 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)