Computing the Width of a Set

Michael E. Houle; Godfried T. Toussaint

doi:10.1109/34.6790

Computing the Width of a Set

Michael E. Houle, Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	761-765
Number of pages	5
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	10
Issue number	5
DOIs	https://doi.org/10.1109/34.6790
State	Published - 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

Access to Document

10.1109/34.6790

Cite this

@article{2fdecd833e684cc4bc7f106acd106d9b,

title = "Computing the Width of a Set",

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.",

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",

author = "Houle, {Michael E.} and Toussaint, {Godfried T.}",

year = "1988",

month = sep,

doi = "10.1109/34.6790",

language = "English (US)",

volume = "10",

pages = "761--765",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

publisher = "IEEE Computer Society",

number = "5",

}

TY - JOUR

T1 - Computing the Width of a Set

AU - Houle, Michael E.

AU - Toussaint, Godfried T.

PY - 1988/9

Y1 - 1988/9

N2 - 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.

AB - 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.

KW - Algorithms

KW - antipodal pairs

KW - artificial intelligence

KW - computational geometry

KW - convex hull

KW - geometric complexity

KW - geometric transforms

KW - image processing

KW - minimax approximating line

KW - minimax approximating plane

KW - pattern recognition

KW - rotating calipers

KW - width

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

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

U2 - 10.1109/34.6790

DO - 10.1109/34.6790

M3 - Article

AN - SCOPUS:0024069812

SN - 0162-8828

VL - 10

SP - 761

EP - 765

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 5

ER -

Computing the Width of a Set

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this