---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Bernard
foaf_name: Chazelle, Bernard
foaf_surname: Chazelle
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Leonidas
foaf_name: Guibas, Leonidas J
foaf_surname: Guibas
- foaf_Person:
foaf_givenName: Micha
foaf_name: Sharir, Micha
foaf_surname: Sharir
- foaf_Person:
foaf_givenName: Jorge
foaf_name: Stolfi, Jorge
foaf_surname: Stolfi
bibo_doi: 10.1007/BF01955043
bibo_issue: '5'
bibo_volume: 15
dct_date: 1996^xs_gYear
dct_publisher: Springer@
dct_title: 'Lines in space: Combinatorics and algorithms@'
...