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

Celý popis

Podrobná bibliografie
Vydáno v:Journal of the ACM 51, 5 (2004).
Hlavní autor: Koltun, Vladlen
Médium: Článek
Jazyk:English
Témata:
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.