Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Q. What is the complexity of finding the largest volume bounded cell in an arrangment of $n$ hyperplanes in dimension $d$?
I feel I should know this... But I am not finding a definitive reference.
Is it $\Omega(n^d)$? How about the $d{=}2$ specialization: The largest area bounded cell in an arrangement of lines?
Somehow doing better than $O(n^d)$ looks hard. If the cell is significantly larger than its average expected size, one can use sampling, to find it. Formally, assume the bounded cells (in the plane) form a polygon of area $1$ (this polygon $Q$ can be computed in near linear time in the plane). Assume the largest bounded cell $C$ in the arrangement of lines has area $\alpha \gg 1/n^2$. Sample, $m = (\log n)/\alpha$ points from $Q$ - and let $P$ be the resulting point set. With high probability one of the points falls inside $C$, and computing all the faces in the arrangement containing points of $P$ takes $O(( n^{2/3} m^{2/3} + n + m)*\mathrm{polylog})$ time using standard magic (i.e., algorithms for computing many faces in the arrangement of lines).
It is now straightforward to apply binary search on $\alpha$, to get an algorithm that computes the largest cell, in time $O\Bigl( \bigl(n + 1/\alpha + n^{2/3}/\alpha^{2/3}\bigr) \mathrm{polylog n}\Bigr)$, where $\alpha$ is the fraction of area of the largest cell out of the total area of the bounded cells (i.e., the area of $Q$).
