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

Question

我一直在努力寻找Longest Arithmetic Subsequence的 2D 版本。

给定一组整数中的二维点，是否有一种有效的算法可以找到这些点的最大子集，这些点形成 NxM矩形网格（例如 7x3、4x4、1x3、2x1、1x1）模式，其中网格大小计算为 NxM ? 请注意，网格图案可以沿 X 和 Y 方向具有不同的步长。此外，单行 (1xM)、单列 (Nx1) 和单个元素 (1x1) 也被视为特殊的矩形网格图案。

对于图中的点，算法应该以红色返回大小为 9 的 3x3 矩形网格图案

非常感谢所有建议和参考！

标签： algorithmpoints

Answer 1

O(n^4)- （仅适用于小点集）解决方案：您可以使用尝试所有点对作为最小元素差的想法。对于 (x1, y1), (x2, y2) 对，您应该构建最大的矩形网格，左上角位于 (x1, y1) 中，带有小矩形width = (x2 - x1)和height = (y2 - y1)。有O(n^2)对。

要构建最大的矩形网格，您可以为左上角位于 (x1, y1) 中的每条可能的 (1xK) 水平线尝试将其尽可能向下扩展。在最坏的情况下也是O(n^2)如此。但是，如果点集中没有长线，它不会那么糟糕。如果解决方案太长，我认为这里有一些优化提示，因为在此算法中，您会多次检查每个单元格。

如果单行和单列的大小不为零，那么您不能使用有关删除点的建议，这些点没有垂直或水平对。