|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions | | Boris Aronov
; Micha Sharir
; | | Date: |
1 Dec 2015 | | Abstract: | Given $n$ non-vertical lines in 3-space, their vertical depth (above/below)
relation can contain cycles. We show that the lines can be cut into
$O(n^{3/2}mathop{mathrm{polylog}} n)$ pieces, such that the depth relation
among these pieces is now a proper partial order. This bound is nearly tight in
the worst case. As a consequence, we deduce that the number of emph{pairwise
non-overlapping cycles}, namely, cycles whose $xy$-projections do not overlap,
is $O(n^{3/2}mathop{mathrm{polylog}} n)$; this bound too is almost tight in
the worst case.
Previous results on this topic could only handle restricted cases of the
problem (such as handling only triangular cycles, by Aronov, Koltun, and
Sharir, or only cycles in grid-like patterns, by Chazelle et al.), and the
bounds were considerably weaker---much closer to quadratic.
Our proof uses a recent variant of the polynomial partitioning technique, due
to Guth, and some simple tools from algebraic geometry. It is much more
straightforward than the previous "purely combinatorial" methods.
Our technique extends to eliminating all cycles in the depth relation among
segments, and of constant-degree algebraic arcs. We hope that a suitable
extension of this technique could be used to handle the (much more difficult)
case of pairwise-disjoint triangles. Our results almost completely settle a
long-standing (35 years old) open problem in computational geometry, motivated
by hidden-surface removal in computer graphics. | | Source: | arXiv, 1512.0358 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER