Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/257

[2] http://www.cs.princeton.edu/research/techreps/author/375

[3] ftp://ftp.cs.princeton.edu/techreports/1992/366.pdf