Algorithms for bichromatic line-segment problems and polyhedral terrains |
| |
Authors: | Bernard Chazelle Herbert Edelsbrunner Leonidas J Guibas Micha Sharir |
| |
Affiliation: | (1) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA;(2) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA;(3) DEC Systems Research Center, 94301 Palo Alto, CA, USA;(4) Computer Science Department, Stanford University, 94305-4055, CA, USA;(5) Courant Institute of Mathematical Sciences, New York University, 10012 New York, NY, USA;(6) School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel |
| |
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.Work on this paper by the first author has been supported in part by the National Science Foundation under Grant CCR-9002352. Work by the second author was supported in part by the National Science Foundation under Grant CCR-8714565. The fourth author has been supported in part by the Office of Naval Research under Grant N0014-87-K-0129, by the National Science Foundation under Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a grant from the US-Israeli Binational Science Foundation. |
| |
Keywords: | Computational geometry Line-segment intersection Segment trees Lines in space Polyhedral terrains Deterministic and randomized algorithms |
本文献已被 SpringerLink 等数据库收录! |
|