3
$\begingroup$

Given a list of compact axis-aligned intervals (in 1-D), rectangles (in 2-D), cuboids (3-D) etc, what is the maximum number that overlap at any point?

In 1-D there's a fairly simple solution that exploits the the ordering of R: assuming you have a set of pairs $\{[a_1,b_1],...,[a_n,b_n]\}$ sort all of the a's and b's (together) then scan from a_min to b_max adding one to the count of overlap whenever you encounter $a_i$ for any i and subtracting one whenever you see a $b_j$ for any j. Then just keep track of the maximum value of count that you see.

I'm not sure how to extend this to 2-D, let alone n-D. Any ideas?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Let $f_{n}(B)$ be an algorithm that solves this problem for a set of $n$D hyperrectangles $B$. If you have $f_n$, you can compute $f_{n+1}$. Let the set of boxes you have be $B$, let $H$ be any set of parallel axis aligned hyperplane, such that the union covers all the vertices of the boxes in $B$. Note $f_{n+1}(B) = \max_{h\in H} \{ f_n (\{ h\cap b: b\in B\}) \}$. This is the exact algorithm you have if $n=1$. $\endgroup$
    – Chao Xu
    Commented Apr 14, 2013 at 1:58
  • $\begingroup$ @ChaoXu Hmm, if I'm understanding you in 2D, if we select H to be to be the simplest set of parallel axis aligned hyperplanes (i.e. lines), we just take lines aligned with the horizontal (say) side of the rectangles (so 2/rectangle). Then we run $f_1$ on each "slice" generated by taking the intersection of each line in H with every rectangle in B and just take the max of that. Clever. I suppose this relies on a generalization of the theorem that in 1-D the point of maximum overlap occurs on an endpoint? (If theres a good proof of that I'd like to see it) $\endgroup$
    – nimish
    Commented Apr 14, 2013 at 2:10
  • 2
    $\begingroup$ It doesn't always occur on an endpoint, for example consider two rectangles that creates a cross shape. You want to prove it occurs at a boundary($\partial$) of the hyperrectangle. A good proof: For any two closed sets $A$ and $B$, $\partial(A\cap B)\subset \partial(A) \cup \partial(B)$. $\endgroup$
    – Chao Xu
    Commented Apr 14, 2013 at 3:46
  • $\begingroup$ So does that mean I need H to contain all sides of every hyperrectangle? Or am I safe with just taking the minimum number needed to cover the vertices? My intuition for the 1-D case is that if you find the maximum overlap in the interior of the overlapping intervals, you can then move infinitesimally to the left or right until you hit an endpoint of some interval. Also, you should put this up as an answer so I can accept it. $\endgroup$
    – nimish
    Commented Apr 14, 2013 at 15:38

2 Answers 2

Reset to default
3
$\begingroup$

Let $f_n(B)$ be an algorithm that solves this problem for a set of $nD$ hyperrectangles $B$. If you have $f_n$, you can compute $f_{n+1}$. Let the set of boxes you have be $B$, let $H$ be any set of parallel axis aligned hyperplane, such that the union covers all the vertices of the boxes in $B$. Note $f_{n+1}(B)=\max_{h\in H}\{f_n(\{h\cap b: b\in B\})\}$. This is the exact algorithm you have if $n=1$.

This works because point intersect most rectangle can be at the boundary of the intersection. You want to prove it occurs at a boundary($\partial$) of the hyperrectangle. A good proof: For any two closed sets $A$ and $B$, $\partial(A\cap B)\subset \partial(A)\cup \partial(B)$.

The above is just the what you need is on the boundaries of the hyperrectangles, but the algorithm are only working with one particular side. You need to show that one side is suffice. This is true because all collection of intersections will contain a side contained in one of the axis aligned halfplane parallel to the original one you have in the beginning. (this would also show intersection of hyerrectangles are hyperrectangles...)

Improve this answer
$\endgroup$
5
$\begingroup$

This is a well-known variant of Klee's measure problem. The best algorithm known, due to Timothy Chan, runs in roughly $O(n^{d/2})$ time, ignoring polylogarithmic factors. Faster algorithms are known for the special cases of fat boxes and boxes with one or more fixed coordinates; see recent work by Karl Bringmann and Hakan Yıldız, respectively.

Improve this answer
$\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.