TY - GEN

T1 - Computing the width of a set

AU - Houle, Michael B.

AU - Toussaint, Godfried T.

PY - 1985/6/1

Y1 - 1985/6/1

N2 - Given a set of points P - {p1,p2....Pn} ,n 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 O(n logn time and O(n) space, where / is the number of antipodal pairs? of edges of the convex hull of P, and in the worst case O(n2). [f P is a set of points in the plane, this complexity can be reduced to O(n logn). Finally, for simple polygons linear time suffices.

AB - Given a set of points P - {p1,p2....Pn} ,n 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 O(n logn time and O(n) space, where / is the number of antipodal pairs? of edges of the convex hull of P, and in the worst case O(n2). [f P is a set of points in the plane, this complexity can be reduced to O(n logn). Finally, for simple polygons linear time suffices.

UR - http://www.scopus.com/inward/record.url?scp=0002569347&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002569347&partnerID=8YFLogxK

U2 - 10.1145/323233.323234

DO - 10.1145/323233.323234

M3 - Conference contribution

AN - SCOPUS:0002569347

T3 - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

SP - 1

EP - 7

BT - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

PB - Association for Computing Machinery, Inc

T2 - 1st Annual Symposium on Computational Geometry, SCG 1985

Y2 - 5 June 1985 through 7 June 1985

ER -