AbstractWe present a simple and practical algorithm for enumerating the set of cells C of an arrangement of m hyperplanes. For fixed dimension its time complexity is O(m|C|). This is an improvement by a factor of m over the reverse search algorithm by Avis and Fukuda. The algorithm needs little space, is output-sensitive, straightforward to parallelize and the implementation is simple for all dimensions.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Additional Key Words and Phrases: cell enumeration, hyperplane arrangement
Selected references
- Herbert Edelsbrunner and Leonidas J. Guibas. Topologically sweeping an arrangement. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 389-403, Berkeley, California, 28-30 May 1986.
- Bernd Gärtner and Emo Welzl. Linear programming -- randomization and abstract frameworks. In 13th Annual Symposium on Theoretical Aspects of Computer Science, volume 1046 of Lecture Notes in Computer Science, pages 669-687, Grenoble, France, 22-24 February 1996. Springer.
- Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, January 1984.
- Thomas Ottmann, S. Schuierer, and S. Soundaralakshmi. Enumerating extreme points in higher dimensions. In 12th Annual Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 562-570, Munich, Germany, 2-4 March 1995. Springer.