Cutting Triangular Cycles of Lines in Space |
| |
| Authors: | Boris Aronov Vladlen Koltun Micha Sharir |
| |
| Institution: | (1) Department of Computer and Information Science, Polytechnic University, Brooklyn, NY 11201-3840, USA;(2) Computer Science Division, University of California, Berkeley, CA 94720-1776, USA;(3) School of Computer Science, Tel Aviv University, Tel-Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA |
| |
| Abstract: | We show that n lines in 3-space can be cut into
O(n2-1/69log16/69n) 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
