# Given a list of intervals, find region that is contained by the largest number of those intervals

Start with 1d case. Say I have lots of 1d intervals $$[s_i, e_i]$$ and I want to find an interval $$[s^*, e^*]$$ to maximise the count of interval $$i$$ such that $$[s_i, e_i]\supseteq [s^*, e^*]$$.

1d case is easy. All I need to do is to sort the $$s_i$$ and $$e_i$$ together, eg $$[s_1, s_2, e_1, s_3, e_3, e_2]$$. Then go from left to right, $$+1$$ if it's $$s$$, $$-1$$ if it's $$e$$. And locate the maximum.

How can I deal with the case in 3d? Here intervals are 3d balls with L1 distance from a point $$\{(x,y,z): |x-x_i|+|y-y_i|+|z-z_i|\leq d_i\}$$.

I can cast it as binary linear programming, but I don't think it's solvable with 1000 binary variables plus 6000 auxiliary variables to deal with absolute value. I wonder if there is a polynomial time solution.

ps: I don't need the entire region, any point inside the max region is good.

• If you had cubes instead, this would be a clear candidate for a sweep line (or plane) algorithm, which is a standard algorithm design technique. These kinds of problems are often solved in computational geometry. – Kirill Dec 24 '18 at 0:08
• @Kirill, I think they are indeed (rotated) cubes – jf328 Dec 24 '18 at 9:56