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

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.

**Links**

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

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

[3] http://www.cs.princeton.edu/research/techreps/author/417

[4] http://www.cs.princeton.edu/research/techreps/author/461

[5] ftp://ftp.cs.princeton.edu/techreports/1990/252.pdf