Computing the width of a set
- 1 September 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 10 (5) , 761-765
- https://doi.org/10.1109/34.6790
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(n/sup 2/). 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
This publication has 6 references indexed in Scilit:
- Computing convolutions by reciprocal searchPublished by Association for Computing Machinery (ACM) ,1986
- Movable Separability of SetsPublished by Elsevier ,1985
- On the ultimate convex hull algorithm in practicePattern Recognition Letters, 1985
- Polygonal approximation by the minimax methodComputer Graphics and Image Processing, 1982
- A linear algorithm for finding the convex hull of a simple polygonInformation Processing Letters, 1979
- Convex hulls of finite sets of points in two and three dimensionsCommunications of the ACM, 1977