Abstract
We show that n lines in 3-space can be cut into O(n2-1/69 log16/69 n) pieces, such that all depth cycles defined by triples of lines are eliminated. This partially resolves a long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics.
Original language | English (US) |
---|---|
Pages (from-to) | 231-247 |
Number of pages | 17 |
Journal | Discrete and Computational Geometry |
Volume | 33 |
Issue number | 2 |
DOIs | |
State | Published - Feb 2005 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics