Chazelle, Bernard ; Edelsbrunner, HerbertIST Austria ; Guibas, Leonidas J ; Sharir, Micha ; Stolfi, Jorge
Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements of n lines in three-dimensional space. Our main results include: 1. A tight Θ(n2) bound on the maximum combinatorial description complexity of the set of all oriented lines that have specified orientations relative to the n given lines. 2. A similar bound of Θ(n3) for the complexity of the set of all lines passing above the n given lines. 3. A preprocessing procedure using O(n2+ε) time and storage, for any ε > 0, that builds a structure supporting O(logn)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the "towering property" in O(n4/3+ε) time, for any ε > 0: do n given red lines lie all above n given blue lines? The tools used to obtain these and other results include Plücker coordinates for lines in space and ε-nets for various geometric range spaces.
NSF Grant CCR-87-00917, NSF Grant CCR-87-14565
428 - 447
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Stolfi J. Lines in space: Combinatorics and algorithms. Algorithmica. 1996;15(5):428-447. doi:10.1007/BF01955043
Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Stolfi, J. (1996). Lines in space: Combinatorics and algorithms. Algorithmica, 15(5), 428–447. https://doi.org/10.1007/BF01955043
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jorge Stolfi. “Lines in Space: Combinatorics and Algorithms.” Algorithmica 15, no. 5 (1996): 428–47. https://doi.org/10.1007/BF01955043.
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi, “Lines in space: Combinatorics and algorithms,” Algorithmica, vol. 15, no. 5, pp. 428–447, 1996.
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Stolfi J. 1996. Lines in space: Combinatorics and algorithms. Algorithmica. 15(5), 428–447.
Chazelle, Bernard, et al. “Lines in Space: Combinatorics and Algorithms.” Algorithmica, vol. 15, no. 5, Springer, 1996, pp. 428–47, doi:10.1007/BF01955043.