从一维案例开始。假设我有很多 1d 间隔$[s_i, e_i]$我想找到一个区间$[s^*, e^*]$最大化间隔计数$i$这样$[s_i, e_i]\supseteq [s^*, e^*]$.

1d 案例很简单。我需要做的就是对$s_i$和$e_i$一起，例如$[s_1, s_2, e_1, s_3, e_3, e_2]$. 然后从左到右，$+1$如果它是$s$,$-1$如果它是$e$. 并找到最大值。

我该如何处理 3d 中的案例？这里的间隔是与一个点的距离为 L1 的 3d 球$\{(x,y,z): |x-x_i|+|y-y_i|+|z-z_i|\leq d_i\}$.

我可以将其转换为二进制线性规划，但我认为用 1000 个二进制变量加上 6000 个辅助变量来处理绝对值是无法解决的。我想知道是否有多项式时间解决方案。

ps：我不需要整个区域，最大区域内的任何一点都可以。