Abstract
We prove tight and near-tight combinatorial complexity bounds for vertical decompositions of arrangements of hyperplanes and 3-simplices in four dimensions. In particular, we prove a tight upper bound of Θ(n4) for the vertical decomposition of an arrangement of n hyperplanes in four dimensions, improving the best previously known bound [8] by a logarithmic factor. We also show that the complexity of the vertical decomposition of an arrangement of n 3-simplices in four dimensions is O(n4 α (n) log2 n), where α (n) is the inverse Ackermann function, improving the best previously known bound [2] by a near-linear factor.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Koltun, V. Sharp Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions. Discrete Comput Geom 31, 435–460 (2004). https://doi.org/10.1007/s00454-003-2871-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-003-2871-3