Abstract
We study combinatorial and algorithmic problems involving arrangements of n lines in 3-dimensional space, and then present applications of our results to a variety of problems on polyhedral terrains. The tools used to obtain the results include Pluecker coordinates for lines in space, random sampling in geometric problems, and a new variant of segment trees.
Original language | English (US) |
---|---|
Title of host publication | Proc Twenty First Annu ACM Symp Theory Comput |
Publisher | Publ by ACM |
Pages | 382-393 |
Number of pages | 12 |
ISBN (Print) | 0897913078 |
State | Published - Dec 1 1989 |
Event | Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA Duration: May 15 1989 → May 17 1989 |
Other
Other | Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing |
---|---|
City | Seattle, WA, USA |
Period | 5/15/89 → 5/17/89 |
All Science Journal Classification (ASJC) codes
- Engineering(all)