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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.