computating the width of a set
Given a set of points P = { p 1 , p 2 ,, p n } 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 &Ogr; ( n log n + I ) time and &Ogr; ( n ) space, where I is the number of antipodal pairs of edges of the convex hull of P , and in the worst case I - &Ogr; ( n 2 ). If P is a set of points in the plane, this complexity can be reduced to &Ogr; ( n log n ). Finally, for simple polygons linear time suffices.
point distance parallel support log timing space convex hull case complexity