Computing the width of a set

Michael B. Houle, Godfried T. Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PublisherAssociation for Computing Machinery, Inc
Pages1-7
Number of pages7
ISBN (Electronic)0897911636, 9780897911634
DOIs
StatePublished - Jun 1 1985
Event1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States
Duration: Jun 5 1985Jun 7 1985

Publication series

NameProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

Other

Other1st Annual Symposium on Computational Geometry, SCG 1985
CountryUnited States
CityBaltimore
Period6/5/856/7/85

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Computing the width of a set'. Together they form a unique fingerprint.

  • Cite this

    Houle, M. B., & Toussaint, G. T. (1985). Computing the width of a set. In Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 (pp. 1-7). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323234