ALGORITHMS FOR BICHROMATIC LINE-SEGMENT PROBLEMS AND POLYHEDRAL TERRAINS

We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range fro m counting the number of intersecting pairs between m blue segments an d n red segments in the plane (assuming that two line segments are dis joint if they have the same color) to finding the smallest vertical di stance between two nonintersecting polyhedral terrains in three-dimens ional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving a rrangements of lines in three-dimensional space, as developed in a com panion paper.