---
_id: '4038'
abstract:
- lang: eng
text: 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.
acknowledgement: Supported in part by the National Science Foundation under Grant
CCR-8714565.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 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
apa: Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1994). Algorithms
for bichromatic line-segment problems and polyhedral terrains. Algorithmica.
Springer. https://doi.org/10.1007/BF01182771
chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
“Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains.” Algorithmica.
Springer, 1994. https://doi.org/10.1007/BF01182771.
ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Algorithms for bichromatic
line-segment problems and polyhedral terrains,” Algorithmica, vol. 11,
no. 2. Springer, pp. 116–132, 1994.
ista: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1994. Algorithms for bichromatic
line-segment problems and polyhedral terrains. Algorithmica. 11(2), 116–132.
mla: 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.
short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Algorithmica 11 (1994)
116–132.
date_created: 2018-12-11T12:06:34Z
date_published: 1994-02-01T00:00:00Z
date_updated: 2022-06-02T12:25:29Z
day: '01'
doi: 10.1007/BF01182771
extern: '1'
intvolume: ' 11'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01182771
month: '02'
oa_version: None
page: 116 - 132
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2089'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithms for bichromatic line-segment problems and polyhedral terrains
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 11
year: '1994'
...