<p>I have always seen this referred to as the depth of an arrangement of boxes (or rectangles in the planar case). Often the algorithms having to do with this depth look somewhat like algorithms for Klee's measure problem, so that can also be a good keyword to search for.</p>
<p>See for example [1] for the best known asymptotic bounds in <span class="math-container">$d$</span> dimensions and for results in the dynamic setting. See [2] for a lower bound in the dynamic setting.</p>
<p>[1] <em>Chan, Timothy M.</em>, <a href="https://doi.org/10.1016/j.comgeo.2009.01.007" rel="nofollow noreferrer"><strong>A (slightly) faster algorithm for Klee’s measure problem</strong></a>, Comput. Geom. 43, No. 3, 243-250 (2010). <a href="https://zbmath.org/?q=an:1180.65022" rel="nofollow noreferrer">ZBL1180.65022</a>.</p>
<p>[2] <em>Dallant, Justin</em> and <em>Iacono, John</em> <a href="https://doi.org/10.4230/LIPIcs.ESA.2022.39" rel="nofollow noreferrer"><strong>Conditional Lower Bounds for Dynamic Geometric Measure Problems</strong></a>, ESA 2022.</p>

CC BY-SA 4.0
2023-10-23T10:22:14.410Z
2023-10-23T10:22:14.410Z
Tassle
<p>There must be a name for this problem, but I can't find it: Given <span class="math-container">$n$</span> rectangles in the plane, what is the most number of rectangles that a point in the plane belongs to? In other words, thinking of some of the boxes as overlapping, what is the greatest depth of the given set of boxes? I am just looking for a name, so I can find efficient storage and computation algorithms, but I would be happy to get algorithms too.</p>

<reference-request>
Finding deepest intersection
femeve3881
# Finding deepest intersection

(Asked by: username_0 on 2023-10-23)

There must be a name for this problem, but I can't find it: Given $n$ rectangles in the plane, what is the most number of rectangles that a point in the plane belongs to? In other words, thinking of some of the boxes as overlapping, what is the greatest depth of the given set of boxes? I am just looking for a name, so I can find efficient storage and computation algorithms, but I would be happy to get algorithms too.

**Tags:** reference-request


---

## 1 answers

### Answer by username_1 on 2023-10-23. Score: 3 | Accepted answer

I have always seen this referred to as the depth of an arrangement of boxes (or rectangles in the planar case). Often the algorithms having to do with this depth look somewhat like algorithms for Klee's measure problem, so that can also be a good keyword to search for.

See for example [1] for the best known asymptotic bounds in $d$ dimensions and for results in the dynamic setting. See [2] for a lower bound in the dynamic setting.

[1] *Chan, Timothy M.*, [**A (slightly) faster algorithm for Klee’s measure problem**](https://doi.org/10.1016/j.comgeo.2009.01.007), Comput. Geom. 43, No. 3, 243-250 (2010). [ZBL1180.65022](https://zbmath.org/?q=an:1180.65022).

[2] *Dallant, Justin* and *Iacono, John* [**Conditional Lower Bounds for Dynamic Geometric Measure Problems**](https://doi.org/10.4230/LIPIcs.ESA.2022.39), ESA 2022.


---

