<p>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). </p>

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

CC BY-SA 3.0
2015-05-30T19:48:27.280Z
Very clever! Even though it only works when $\alpha \gg 1/n^2$.
Joseph O'Rourke
CC BY-SA 3.0
2015-05-30T19:17:24.330Z
2015-05-30T19:17:24.330Z
Sariel Har-Peled
<blockquote>
  <p><strong><em>Q</em></strong>. What is the complexity of finding the largest volume bounded cell in an arrangment of
  $n$ hyperplanes in dimension $d$?</p>
</blockquote>

<p>I feel I should know this... But I am not finding a definitive reference.</p>

<p>Is it $\Omega(n^d)$?
How about the $d{=}2$ specialization:
The largest area bounded cell in an arrangement of lines?</p>

<computational-geometry><high-dimensional-geometry><arrangements>
Largest cell in an arrangement
Joseph O'Rourke
# Largest cell in an arrangement

(Asked by: username_0 on 2015-03-13)

> ***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?

**Tags:** computational-geometry, high-dimensional-geometry, arrangements

---

## 1 answers

### Answer by username_1 on 2015-05-30. Score: 6

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

> **Comments:**
> **username_0**: Very clever! Even though it only works when $\alpha \gg 1/n^2$.  

---

