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

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

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

CC BY-SA 3.0
2013-04-23T05:53:37.677Z
2013-04-23T05:59:43.997Z
2013-04-23T05:59:43.997Z
Chao Xu
<p>This is a well-known variant of <a href="http://en.wikipedia.org/wiki/Klee%27s_measure_problem">Klee's measure problem</a>.  The best algorithm known, due to <a href="https://cs.uwaterloo.ca/~tmchan/pub_klee.html">Timothy Chan</a>, 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 <a href="http://www.mpi-inf.mpg.de/~kbringma/">Karl Bringmann</a> and <a href="http://www.cs.ucsb.edu/~hakan/">Hakan Yıldız</a>, respectively.</p>

CC BY-SA 3.0
2013-04-23T17:48:32.897Z
2013-04-23T17:48:32.897Z
Jeffε
<p>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?</p>

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

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

CC BY-SA 3.0
2013-04-14T01:58:08.110Z
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$.
Chao Xu
CC BY-SA 3.0
2013-04-14T02:10:01.950Z
@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)
nimish
CC BY-SA 3.0
2013-04-14T03:46:49.573Z
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)$.
Chao Xu
CC BY-SA 3.0
2013-04-14T15:38:27.483Z
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.
nimish
<cg.comp-geom>
Number of Maximum Overlap in n-Dimensions
nimish
# Number of Maximum Overlap in n-Dimensions

(Asked by: username_0 on 2013-04-14)

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?

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: 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$.  
> **username_0**: @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)  
> **username_1**: 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)$.  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_1 on 2013-04-23. Score: 3 | Accepted answer

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


---

### Answer by username_2 on 2013-04-23. Score: 5

This is a well-known variant of [Klee's measure problem](http://en.wikipedia.org/wiki/Klee%27s_measure_problem). The best algorithm known, due to [Timothy Chan](https://cs.uwaterloo.ca/~tmchan/pub_klee.html), 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](http://www.mpi-inf.mpg.de/~kbringma/) and [Hakan Yıldız](http://www.cs.ucsb.edu/~hakan/), respectively.


---

