Computing the width of a set |
| |
Authors: | Houle ME Toussaint GT |
| |
Affiliation: | Sch. of Comput. Sci., McGill Univ., Montreal, Que. ; |
| |
Abstract: | 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 a 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 |
| |
Keywords: | |
|
|