Finding the smallest polygon covering a set of points in a grid

Question

Firstly, I am not asking for code, I just want to clarify my approach.

Secondly, if it is not completely related to SO, I will transfer the question to the most appropriate Stack Exchange site. I am sure this is a problem with graph theory.

So I have an infinitely large grid with a specific point (0,0)

Each intersection of horizontal / vertical lines in the grid defines a different point (given by the number of lines from the origin).

Given the set of points (x,y) , where each x,y is an integer: return the perimeter of the smallest polygon surrounding the points.

Limitations:

• Number of points less than 100,000
• Points cannot lie around the perimeter of a polygon.
• The sides of the polygon can only correspond to vertical / horizontal lines in a grid or a diagonal line in one square.

My guess is that the problem is with the graphics. Like Traveling Salesman, I first need to find the shortest path between all points, using an algorithm that gives an optimal solution. Then I need to execute the same algorithm between each point in order to find the optimal path along the grid between the points.

I wrote an algorithm for a Traveler in 80 cities.

There may be 100,000 points in this question. Therefore, it surprises me if there is a possible algorithm for solving such a huge number of nodes.

Is there any other approach. Am I thinking about it wrong?

Thanks for any help!

Answer 1

Convex hull is not really required to solve this problem.

The most efficient Convex hull algorithm is O(nlogh) , where n is the number of points in total and h is the number of points on the case.

Looking through the comments above, m69 nailed it! The algorithm that he describes (with a slightly larger top) can be achieved in O(n) time. Drop the idea of Convex hull !

• Draw a minimal square so that it surrounds all the points indicated. This is done using max and min in the point list.
• For each corner squared, draw an allowed diagonal line closest to the outermost point. This is done by scrolling through the points and using the Euclidean formula perpendicular to the distance. This is O(n)
• Using the intersections between the original square and the diagonal lines, calculate the total perimeter of the polygon.

Here is my version of the algorithm (written in python). People can comment or optimize if they wish. It was a fun problem.

 from math import * N = int(raw_input()) pts = [] for i in xrange(N): p1,p2 = map(int, raw_input().split(' ')) pts.append((p1,p2)) def isBetween(a, b, c): ab = sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) ac = sqrt((a[0]-c[0])**2 + (a[1]-c[1])**2) bc = sqrt((b[0]-c[0])**2 + (b[1]-c[1])**2) return abs(ac + bc - ab) < 0.01 # epsilon precision, needs < 1 in grid case def getPoints(c): lines = [(-1, c[0][1]+c[0][0]),(1, c[1][1]-c[1][0]),(-1,c[2][1]+c[2][0]),(1,c[3][1]-c[3][0])] maxes = [[0,0],[0,0],[0,0],[0,0]] for count, line in enumerate(lines): pdist = (abs(line[0]*CH[0][0] - CH[0][1] + line[1]))/(sqrt((line[0]*line[0]) + 1 )) maxes[count][0] = pdist maxes[count][1] = CH[0] for elem in CH[1:]: for count, line in enumerate(lines): pdist = (abs(line[0]*elem[0] - elem[1] + line[1]))/(sqrt((line[0]*line[0]) + 1 )) if pdist < maxes[count][0]: maxes[count][0] = pdist maxes[count][1] = elem for greg in range(4): maxes[greg][1] = list(maxes[greg][1]) maxes[0][1][0] -=1 maxes[1][1][0] +=1 maxes[2][1][0] +=1 maxes[3][1][0] -=1 gregarr = [] for i in range(4): y = lines[i][0]*(c[i][0]-maxes[i][1][0]) + maxes[i][1][1] cornerdist = abs(c[i][1] - y) if i == 0: gregarr.append((c[i][0], c[i][1]+cornerdist)) gregarr.append((c[i][0]+cornerdist, c[i][1])) elif i == 1: gregarr.append((c[i][0]-cornerdist, c[i][1])) gregarr.append((c[i][0], c[i][1]+cornerdist)) elif i == 2: gregarr.append((c[i][0], c[i][1]-cornerdist)) gregarr.append((c[i][0]-cornerdist, c[i][1])) else: gregarr.append((c[i][0]+cornerdist, c[i][1])) gregarr.append((c[i][0], c[i][1]-cornerdist)) return gregarr def distance(p0, p1): return ((p0[0] - p1[0])*(p0[0] - p1[0]) + (p0[1] - p1[1])*(p0[1] - p1[1]))**(0.5) def f7(seq): seen = set() seen_add = seen.add return [ x for x in seq if not (x in seen or seen_add(x))] CH = pts H = len(CH) if H == 0: print('0.000') elif H == 1: print('5.656') else: per = 0 minx = min(CH, key = lambda x: x[0])[0]-1 miny = min(CH, key = lambda x: x[1])[1]-1 maxx = max(CH, key = lambda x: x[0])[0]+1 maxy = max(CH, key = lambda x: x[1])[1]+1 corners = [(minx,miny),(maxx, miny),(maxx,maxy),(minx,maxy)] arr = getPoints(corners) arr = f7(arr) arr.append(arr[0]) T = len(arr) for i in range(1,T): per += distance(arr[i-1], arr[i]) print(per)