Answers are grounded in this paper and cite their sources.
Given a set of points P = {p1,p2,…,pn} in three dimensions, 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 Ο(n log n + I) time and Ο(n) space, where I is the number of antipodal pairs of edges of the convex hull of P, and in the worst case I - Ο(n2). If P is a set of points in the plane, this complexity can be reduced to Ο(n log n). Finally, for simple polygons linear time suffices.
No takes yet. Share an insight, caveat, or question.
Houle et al. (1985) studied this question.