Algorithms for Bichromatic Line Segment Problems and Polyhedral Terrains
Report ID: TR-252-90Author: Chazelle, Bernard / Edelsbrunner, Herbert / Guibas, Leonidas / Sharir, Micha
Date: 1990-03-00
Pages: 16
Download Formats: |PDF|
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.