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).
المؤلف الرئيسي:	Koltun, Vladlen
التنسيق:	مقال
اللغة:	English
الموضوعات:	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.