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)