algorithm - 从一组二维点中找到最大的矩形网格图案

Question

我一直在努力寻找 Longest Arithmetic Subsequence 的 2D 版本.
给定 中的一组二维点整数 ，是否有一种有效的算法可以找到 最大子集这些点中形成 NxM 矩形网格(例如 7x3、4x4、1x3、2x1、1x1)模式，其中网格大小计算为 NxM？请注意，网格图案沿 X 和 Y 方向可以具有不同的步长。此外，单行 (1xM)、单列 (Nx1) 和单个元素 (1x1) 也被视为特殊的矩形网格图案。
对于图中的点，算法应返回大小为 9 的红色 3x3 矩形网格图案

非常感谢所有建议和引用!

Answer 1

O(n^4) -(仅适用于小点集)解决方案:
你可以用这个idea尝试所有点对作为最小元素的差异。对于 (x1, y1), (x2, y2) 对，您应该在 (x1, y1) 中构建左上角的最大矩形网格和小矩形 width = (x2 - x1)和 height = (y2 - y1) .有O(n^2)对。
要构建最大的矩形网格，您可以为 (x1, y1) 中的每条可能的 (1xK) 水平线(x1，y1)尝试将其向下扩展。在最坏的情况下是 O(n^2)也。但如果点集中没有长线，也不会那么糟糕。如果解决方案太长，我认为这里有一些优化提示，因为在这个算法中你会多次检查每个单元格。
如果单行和单列的大小不为零，则您不能使用有关删除点的建议，这些点没有垂直或水平对。