Find the largest rectangular grid pattern from a set of 2D points

user_2368570 0
Viewed 189

I have been struggling with the 2D version of finding Longest Arithmetic Subsequence .

Given a set of 2D points in integers, is there an efficient algorithm that finds the largest subset of these points that form a NxM rectangular grid (e.g. 7x3, 4x4, 1x3, 2x1, 1x1) pattern, where the grid size is calculated as NxM? Note that the grid pattern can have different step sizes along X and Y directions. Also, single row (1xM), single column (Nx1) and single element (1x1) are also considered special rectangular grid patterns.

For points in the figure, the algorithm should return the 3x3 rectangular grid pattern of size 9 in red

2

All suggestions and references are greatly appreciated!

points algorithm
1 Answers

O(n^4) - (fits only for tiny points sets) solution: You can use this idea of trying all point pairs as difference of minimal element. For pair (x1, y1), (x2, y2) you should build largest rectangular grid with top left corner in (x1, y1) with small rectangle width = (x2 - x1) and height = (y2 - y1). There is O(n^2) pairs.

To build largest rectangular grid you can for every possible (1xK) horisontal line with top left corner in (x1, y1) try to expand it down as long as possible. In worst case it's O(n^2) too. But it will be not so bad, if there is no long lines in the points set. I think here lies some optimization hints if solution will be too long, because in this algorithm you check each cell many times.

if single rows and columns have non zero size, so you cannot use advice about deleting points, which hasn't vertical or horisontal pair.

user_77907400
Related