Lines in Space: Combinatorics and Algorithms

Bernard Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, J. Stolfi

Research output: Contribution to journalArticle

40 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)428-447
Number of pages20
JournalAlgorithmica (New York)
Volume15
Issue number5
DOIs
StatePublished - Jan 1 1996

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Lines in Space: Combinatorics and Algorithms'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Edelsbrunner, H., Guibas, L. J., Sharir, M., & Stolfi, J. (1996). Lines in Space: Combinatorics and Algorithms. Algorithmica (New York), 15(5), 428-447. https://doi.org/10.1007/BF01955043