Almost tight upper bounds for vertical decompositions in four dimensions.

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...

Deskribapen osoa

Xehetasun bibliografikoak
Argitaratua izan da:Journal of the ACM 51, 5 (2004).
Egile nagusia: Koltun, Vladlen
Formatua: Artikulua
Hizkuntza:English
Gaiak:
Mathematics of computing.
Discrete mathematics.
Combinatorics.
Combinatorial algorithms.
Counting problems.
Computing methodologies.
Computer graphics.
Computational geometry and object modeling.
Geometric algorithms, languages and systems.
Algorithms.
Theory.