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

Fuld beskrivelse

Bibliografiske detaljer
Udgivet i:Journal of the ACM 51, 5 (2004).
Hovedforfatter: Koltun, Vladlen
Format: Article
Sprog:English
Fag:
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.