ISSN:
1432-0541
Keywords:
Computational geometry
;
Line-segment intersection
;
Segment trees
;
Lines in space
;
Polyhedral terrains
;
Deterministic and randomized algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 andn 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 nonintersecting polyhedral terrains in three-dimensional 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 arrangements of lines in three-dimensional space, as developed in a companion paper.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01182771
Permalink
