Algorithms for bichromatic line-segment problems and polyhedral terrains

B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Algorithmica 11 (1994) 116–132.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ;
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 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.
Publishing Year
Date Published
1994-02-01
Journal Title
Algorithmica
Acknowledgement
Supported in part by the National Science Foundation under Grant CCR-8714565.
Volume
11
Issue
2
Page
116 - 132
IST-REx-ID

Cite this

Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica. 1994;11(2):116-132. doi:10.1007/BF01182771
Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1994). Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica, 11(2), 116–132. https://doi.org/10.1007/BF01182771
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains.” Algorithmica 11, no. 2 (1994): 116–32. https://doi.org/10.1007/BF01182771.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Algorithms for bichromatic line-segment problems and polyhedral terrains,” Algorithmica, vol. 11, no. 2, pp. 116–132, 1994.
Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1994. Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica. 11(2), 116–132.
Chazelle, Bernard, et al. “Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains.” Algorithmica, vol. 11, no. 2, Springer, 1994, pp. 116–32, doi:10.1007/BF01182771.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar