Home Bookmarks Papers Blog

Minimum Area Rectangle, Diameter, ...

Applet By Nir Efrat


This applet demonstrate how to compute various really interesting properties of a point set in the plane. In particular: 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.

Algorithms descriptions

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.

Diameter

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:

  1. The first pair will consist of the leftmost and the rightmost points. We draw two vertical lines thru them.
  2. Now, at each step, we rotate the parallel lines in the minimal angle which changes the pair of antipodal points that are defined by the lines.
  3. We finish when we complete a whole round.

Minimum Width

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).

  1. For each pair, we'll find the distance between the two lines, and the width is the minimal distance.
  2. We'll find the pairs in the following way:
  3. The first pair will consist of two vertical lines that go thru the most left and the most right points.
  4. 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 Rectangule

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 calculated.
The first rect will lie on the most right, most left, most up and most down points.
For each rect we'll calculate the area and the circumference. This way we can find the minimum.

The Applet


This applet is best viewed at 800x600 resolution.
How to use the applet
The complete source of the applet
Back to the Workshop home page