Optimal Algorithms for Computing Connected Components of Bichromatic Line Segments and Polygons
Report ID: TR-366-92Author: Zhao, Jenny Zehong / Dobkin, David P.
Date: 1992-03-00
Pages: 9
Download Formats: |PDF|
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.