Optimal Algorithms for Computing Connected Components of Bichromatic Line Segments and Polygons

Abstract:

A set of planar geometric objects can be partitioned into connected components,
where these are defined by the reflective transitive closure of the pairwise
intersection or overlap relation. We consider the problem of finding
connected components of the union between $m$ blue line segments and $n$
red line segments in the plane, assuming that two line segments are disjoint
if they have the same color. We solve this problem in $O(N$ log $N)$
time and $O(N)$ space, where $N = m+n$, by using a variant of thesetment
tree and union-find technique. It is then generalized to determine, in
the same time and space bounds, the connected components of bichromatic simple
polygons with $N$ sides total, where polygons with the same color do not
intersect or overlap.