--- _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' ...