I am given a lot of points and the points are suppose to be from a rectangle. I'm required to calculate the boundary of the rectangle. Moreover, I have to figure out radius of an empty candle(cylindrical) that could be anywhere in the rectangle. All of this from just the given points. I would appreciate if someone could suggest ways to achieve this.
The points in my case are measurements of a robot wandering through this rectangle, and the empty circle is a pole of a certain unknown radius inside the rectangle that the robot can hit. So I need to figure out the radius of the pole in order to avoid that. I need to estimate the pole. It doesn't have to be exact. I'm expecting robot measurements to be enough that they'd give me pretty good idea where pole is.
Your first question seems to be about finding the smallest rectangle containing a point cloud.
One solution is to find the convex hull of the points and then find the smallest rectangle containing the hull. See Minimum-Area Rectangle Containing a Set of Points.
Alternatively, find the orientation of the rectangle using principal component analysis on the point cloud, then find the sides by finding the points farthest from the center of the cloud in the two directions found by PCA.
These two rectangles do not always coincide: the one computed by PCA usually larger but is probably easier to code.
Your second problem is the largest empty circle problem, for which exist efficient algorithms based on the Voronoi diagram: the center of the circle is the Voronoi vertex with largest empty circle. See for instance section 6.4 "Gaps and Covers" of the book Computational Geometry by Preparata and Shamos.