This applet demonstrate how to compute various really interesting properties of a point
set in the plane. In particular:
Compute the two points of our set that their distance is
Compute all the pair of points in the set,
such that the two lines penpendicular to the segment connecting
the points also
contains the whole set of points (strange, but...).
Compute the minimum area rectangle that contains
all the points
Compute the rectangle with minimum Circumference
(i.e. perimeter) rectangle that contains all the points.
Find the two closest parallel lines that contains the set.
All those things can be performed in the amazing complexity of O(n
log n). In fact, once the convex-hull is computed all those tasks
can be computed in linear time.
All the five properties we'll find depends merely on the convex-hull
of the set of points. It's obvious that inner points (points which
doesn't belong to the convex hull) cannot affect (participate in) the
maximum distance between two points, the minimum width etc.
Therefore, we'll compute the convex hull and run the algorithms only
on the smaller set of the points that belong to the convex-hull.
The basic algorithm is described in:
G.T. Toussaint,Solving geometric problems with the rotating calipers,
In Proc. IEEE MELECON '83, A10.02/1-4, 1983.
First, we define "antipodal points" to be two points (that belong to
the convex hull) thru which we can draw two parallel lines which don't
intersect the polygon (beside those two point). It is clear that the
most distant dots will be antipodal.
Now, we'll check all of the antipodal pairs of points
( O(n) ). For each pair we'll find the distance between the two points,
and so we'll find the maximum distance.
We go through the pairs in the following way:
The first pair will consist of the leftmost and the rightmost
points. We draw two vertical lines thru them.
Now, at each step, we rotate the parallel lines in the minimal
angle which changes the pair of antipodal points that are defined by
We finish when we complete a whole round.
The minimum width is the distance between the closest parallel
lines between which all of the point are placed.
To find the minimal width, we'll go through a sequence
of pairs of parallel lines the hold all of the points between them. In
each pair, one of the lines must coincide with a polygon edge. The
other line will be the most distant line that still touches the polygon
(There are at most n pairs).
For each pair, we'll find the distance between the two
lines, and the width is the minimal distance.
We'll find the pairs in the following way:
The first pair will consist of two vertical lines that
go thru the most left and the most right points.
Then, for each pair, (exactly like in the diameter) we rotate
the two parallel lines in the angle that move one line to lie on
a new edge.
Minimum area or circumference
By computing a formula, deriving and finding the minimum, one can
prove that the minimum rects will always have at least one side that
lies on a polygon edge.
In order to find the minimum area or circumference blocking
rectangule, we'll examine a sequence of such rectangles. The basic
idea is to start with a bounding rectangle and to rotate it at each
step, so we'll change only one point from the polygon's points that
lie on the rect. We do that by calculating the angles for each point
between the rect side that lies on it and the next polygon edge
(clockwise). We rotate the rect in the minimal angle we've
The first rect will lie on the most right, most left, most up and most
For each rect we'll calculate the area and the circumference. This way
we can find the minimum.