Computing the Width of a Set

Michael E. Houle, Godfried T. Toussaint

Research output: Contribution to journalArticle

Abstract

Given a set of points P = { p1, p2, · · ·, pn} 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 0(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 in the worst case I = Ω(n2). For convex polyhedra, the time complexity becomes 0(n + I). If P is a set of points in the plane, the complexity can be reduced to 0(n log n). Finally, for simple polygons linear time suffices.

Original languageEnglish (US)
Pages (from-to)761-765
Number of pages5
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume10
Issue number5
DOIs
StatePublished - Sep 1988

Keywords

  • Algorithms
  • antipodal pairs
  • artificial intelligence
  • computational geometry
  • convex hull
  • geometric complexity
  • geometric transforms
  • image processing
  • minimax approximating line
  • minimax approximating plane
  • pattern recognition
  • rotating calipers
  • width

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics

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

Cite this