0
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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, Comput. Geom. 43, No. 3, 243-250 (2010). ZBL1180.65022.

[2] Dallant, Justin and Iacono, John Conditional Lower Bounds for Dynamic Geometric Measure Problems, ESA 2022.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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