Exact and approximation algorithms for minimum-width cylindrical shells

P. K. Agarwal; B. Aronov; M. Sharir

doi:10.1007/s00454-001-0039-6

Exact and approximation algorithms for minimum-width cylindrical shells

P. K. Agarwal, B. Aronov, M. Sharir

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

Abstract

Let S be a set of n points in ℝ³. Let ω* be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first present an O(n⁵)-time algorithm for computing ω*, which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n^2+δ)-time algorithm, for any δ > 0, that computes a cylindrical shell of width at most 56ω* containing S.

Original language	English (US)
Pages (from-to)	307-320
Number of pages	14
Journal	Discrete and Computational Geometry
Volume	26
Issue number	3
DOIs	https://doi.org/10.1007/s00454-001-0039-6
State	Published - Oct 2001

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-001-0039-6

Cite this

@article{88364e74cf6d4e9a994db66af913e39b,

title = "Exact and approximation algorithms for minimum-width cylindrical shells",

abstract = "Let S be a set of n points in ℝ3. Let ω* be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first present an O(n5)-time algorithm for computing ω*, which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n2+δ)-time algorithm, for any δ > 0, that computes a cylindrical shell of width at most 56ω* containing S.",

author = "Agarwal, {P. K.} and B. Aronov and M. Sharir",

year = "2001",

month = oct,

doi = "10.1007/s00454-001-0039-6",

language = "English (US)",

volume = "26",

pages = "307--320",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Exact and approximation algorithms for minimum-width cylindrical shells

AU - Agarwal, P. K.

AU - Aronov, B.

AU - Sharir, M.

PY - 2001/10

Y1 - 2001/10

N2 - Let S be a set of n points in ℝ3. Let ω* be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first present an O(n5)-time algorithm for computing ω*, which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n2+δ)-time algorithm, for any δ > 0, that computes a cylindrical shell of width at most 56ω* containing S.

AB - Let S be a set of n points in ℝ3. Let ω* be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first present an O(n5)-time algorithm for computing ω*, which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n2+δ)-time algorithm, for any δ > 0, that computes a cylindrical shell of width at most 56ω* containing S.

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

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

U2 - 10.1007/s00454-001-0039-6

DO - 10.1007/s00454-001-0039-6

M3 - Article

AN - SCOPUS:0035618009

SN - 0179-5376

VL - 26

SP - 307

EP - 320

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

Exact and approximation algorithms for minimum-width cylindrical shells

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this