Sharp bounds for vertical decompositions of linear arrangements in four dimensions (Q701796)

The author investigates combinatorial complexity bounds for vertical decompositions of arrangements of hyperplanes and 3-simplices in four dimensions. Many geometric algorithms require arrangements to be decomposed into cells of constant description complexity. The author proves a tight upper bound of \(\Theta(n^4)\) for the vertical decomposition of an arrangement of \(n\) hyperplanes in four dimensions. For the case of \(n\) 3-simplices in four dimensions a complexity bound of \(O(n^4 \alpha(n) \log^2 n)\) can be shown, where \(\alpha(n)\) is the inverse Ackermann function. Both results improve previously known bounds.