COMPUTING THE WIDTH OF A SET

For a set of points P in three-dimensional space, the width of P, W(P), is defined as the minimum distance between parallel planes of support of P. It is shown that W(P) can be computed in O(n log n + I) time and O(n) space, where I is the number of antipodal pairs of edges of the convex hull of P, and n is the number of vertices; in the worst case, I = O(n2). For convex polyhedra the time complexity becomes O(n + I). If P is a set of points in the plane, the complexity can be reduced to O(nlog n). For simple polygons, linear time suffices.