## 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 Θ(n^{2}) 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 Θ(n^{3}) for the complexity of the set of all lines passing above the n given lines. 3. A preprocessing procedure using O(n^{2+ε}) 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(n^{4/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 language | English (US) |
---|---|

Pages (from-to) | 428-447 |

Number of pages | 20 |

Journal | Algorithmica (New York) |

Volume | 15 |

Issue number | 5 |

DOIs | |

State | Published - Jan 1 1996 |

## All Science Journal Classification (ASJC) codes

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