Question

Let s be a set of N points in the plane with integer coordinates between 1 and N", where d is a constant. Show that the convex hull of S can be found in linear time

Answer 1

The convex hull of a set of points with integer coordinates lying between 1 to N^2, where d is constant, can be found in linear time using an optimized version of Andrew's monotone chain algorithm.

Step-by-step explanation:

The question pertains to computational geometry, specifically to the problem of finding the convex hull of a set of points, S, in the plane with integer coordinates. Assuming d is a constant and the coordinates of points lie between 1 and N2, one can use a variation of Andrew's monotone chain algorithm to compute the convex hull in linear time, O(N). The algorithm works by first sorting the points lexicographically by their x-coordinates and then combining the upper and lower hulls generated by a two-pass procedure. Although the standard algorithm runs in O(N log N) due to the sort step, the unique constraint that the number of points is bounded by N2 implies a specific property of integer grids that allows for the sorting step to be optimized to linear time using integer-sorting algorithms such as counting sort.