Exact and approximation algorithms for minimum-width cylindrical shells

Pankaj K. Agarwal; Boris Aronov; Micha Sharir

Exact and approximation algorithms for minimum-width cylindrical shells

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Let S be a set of n points in R³. Let ω* = ω*(S) 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 26(1+1/n^4/9)ω* containing S.

Original language	English (US)
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher	SIAM
Pages	510-517
Number of pages	8
State	Published - 2000
Event	11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: Jan 9 2000 → Jan 11 2000

Other

Other	11th Annual ACM-SIAM Symposium on Discrete Algorithms
City	San Francisco, CA, USA
Period	1/9/00 → 1/11/00

ASJC Scopus subject areas

Chemical Health and Safety
Software
Safety, Risk, Reliability and Quality
Discrete Mathematics and Combinatorics

Cite this

@inproceedings{346fb1a68efd4c15b420234a1753ea29,

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

abstract = "Let S be a set of n points in R3. Let ω* = ω*(S) 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 26(1+1/n4/9)ω* containing S.",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Micha Sharir",

year = "2000",

language = "English (US)",

pages = "510--517",

booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "SIAM",

note = "11th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 09-01-2000 Through 11-01-2000",

}

TY - GEN

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

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Sharir, Micha

PY - 2000

Y1 - 2000

N2 - Let S be a set of n points in R3. Let ω* = ω*(S) 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 26(1+1/n4/9)ω* containing S.

AB - Let S be a set of n points in R3. Let ω* = ω*(S) 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 26(1+1/n4/9)ω* containing S.

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

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

M3 - Conference contribution

AN - SCOPUS:0033881364

SP - 510

EP - 517

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

PB - SIAM

T2 - 11th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 9 January 2000 through 11 January 2000

ER -

Exact and approximation algorithms for minimum-width cylindrical shells

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this