10
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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$).

$\endgroup$
  • 1
    $\begingroup$ Very clever! Even though it only works when $\alpha \gg 1/n^2$. $\endgroup$ – Joseph O'Rourke May 30 '15 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.