Output-sensitive cell enumeration in hyperplane arrangements
Nora Sleumer · Nordic journal of computing · 1999
We 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.