Dav*_*ein 8 algorithm computational-geometry
在这个问题中,r是一个固定的正整数.在平面中给出N个矩形,大小相同.侧面可以是垂直的也可以是水平的.我们假设所有N个矩形的交叉区域具有非零区域.问题是如何找到这些矩形的Nr,以便最大化交叉区域.当实际显微镜中的一个重复成像给定的生物样本时,这个问题出现,并且由于物理原因(例如显微镜和相机的部件的不同扩展),在该过程期间对准稍微改变.我已经表达了维度d = 2的问题.每个d> 0都存在类似的问题.对于d = 1,通过对间隔的左手端点进行排序来获得O(N log(N))解.但是我们坚持使用d = 2.如果r = 1,则可以通过对角的坐标进行排序来再次解决时间O(N log(N))的问题.
因此,通过首先解决案例(N,1)获得N-1个矩形,然后解决案例(N-1,1),获得N-2个矩形等来解决原始问题,直到我们减少到Nr矩形？我有兴趣看到这个乐观尝试过程的明确反例.如果程序有效会更有意思(请证明!),但这似乎过于乐观了.
如果r固定在某个值r> 1,并且N很大,那么NP类中的一个是这个问题吗？
感谢您对此的任何想法.
大卫
小智 4
由于轴对齐矩形的交集是轴对齐矩形，因此存在 O(N 4 ) 个可能的交集（O(N) 左、O(N) 右、O(N) 上、O(N) 下）。显而易见的 O(N 5 ) 算法是尝试所有这些，检查每个是否包含在至少 N - r 个矩形中。
对 O(N 3 )的改进是尝试X 维度中的所有 O(N 2 ) 间隔，并在包含给定 X 间隔的那些矩形上在 Y 维度中运行 1D 算法。（矩形只需排序一次。）
N 有多大？我预计奇特的数据结构可能会导致 O(N 2 log N) 算法，但如果三次算法就足够了，那就不值得你花时间了。