- If you are looking for the problem of finding the convex hull of a finite set of points, take a look at here. You can find several solutions to do this in O(n*log n)
If you are just looking for the four corners of the bounding rectangle of this convex hull, actually you are looking for minimum bounding box for the convex hull.
If the bounding box is parallel to the coordinate axes, just find the
min_x
,min_y
,max_x
andmax_y
among all these convex hull points. Then the four corners (clockwisely) are:(min_x, min_y)
(max_x, min_y)
(max_x, max_y)
(min_x, max_y)