LINES IN-SPACE - COMBINATORICS AND ALGORITHMS

Questions about lines in space arise frequently as subproblems in thre e-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrang ements of n lines in three-dimensional space. Our main results include : 1. A tight Theta(n(2)) bound on the maximum combinatorial descriptio n complexity of the set of all oriented lines that have specified orie ntations relative to the n given lines. 2. A similar bound of Theta(n( 3)) for the complexity of the set of all lines passing above the n giv en lines. 3. A preprocessing procedure using O(n(2+epsilon)) time and storage, for any epsilon > 0, that builds a structure supporting O(log n)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the ''towering property'' in O(n(4/3+epsil on)) time, for any epsilon > 0: do n given red lines lie all above n g iven blue lines? The tools used to obtain these and other results incl ude Plucker coordinates for lines in space and epsilon-nets for variou s geometric range spaces.