Minimal Bounding Shapes in 2 and 3
Dimensions
John R. D’Errico
Email: woodchips@rochester.rr.com
January 28, 2007
1 Introduction - Minimal Bounding Shapes
This document will discuss the estimation of several basic enclosing shapes
around sets of points in 2 and 3 dimensions.
But first, why would you wish to use these tools at all? A minimal
enclosing object of a well defined basic shape may be of use to roughly char-
acterize objects, perhaps in an image. Perhaps one needs simple e stimate s
of an area enclosed, or of the center of a roughly circular or elliptical object.
Some examples might be bacteria, crystals, granular particles, film grain,
etc.
The basic codes I’ll discuss are:
• Rectangles - MINBOUNDRECT
• Circles - MINBOUNDCIRCLE
• Spheres (3-d) - MINBOUNDSPHERE
• Ellipses - MINBOUNDELLIPSE
• Ellipsoids (3-d) - MINBOUNDELLIPSOID
One feature that all these codes have in common is the initial use of a
convex hull call. Since all of the s hapes we will consider here are convex
objects, no point that is inside the convex hull of the data set need be
considered. Removal of those interior data points will often result in a
dramatic reduction in the time required otherwise.
1
