Almost tight upper bounds for vertical decompositions in four dimensions.
We show that the complexity of the vertical decomposition of an arrangement of n fixed-degree algebraic surfaces or surface patches in four dimensions is O(n4+ϵ), for any ϵ > 0. This improves the best previously known upper bound for this problem by a near-linear factor, and s...
| 發表在: | Journal of the ACM 51, 5 (2004). |
|---|---|
| 主要作者: | |
| 格式: | Article |
| 語言: | English |
| 主題: |