Algorithms for Bichromatic Line Segment Problems and Polyhedral Terrains

Abstract:

We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments and n red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two non-intersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a varient of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.