3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Kirill Dec 24 '18 at 0:08
  • $\begingroup$ @Kirill, I think they are indeed (rotated) cubes $\endgroup$ – jf328 Dec 24 '18 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.