Geometry / Arrangement (Bibtex)

P322: Enumeration of all cells in arrangements

Input:

An arrangement of distinct hyperplanes.

Output:

All cells in arrangements.

Complexity:

$O(nm\ell(n,m)N)$ total time and $O(nm)$ space.

Comment:

$n$ is the dimension, $m$ is the number of hyperplanes, and $\ell(n, m)$ is the time for solving an LP with $n$ variables and $m-1$ inequalities. $N$ is the number of solutions.

Reference:

[Avis1996] (Bibtex)