Math @ Duke

Publications [#235426] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M, Exact and approximation algorithms for minimumwidth cylindrical shells,
in Eleventh Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2000),
pp. 510517
(last updated on 2017/12/15)
Abstract: Let S be a set of n points in R3. Let ω* = ω*(S) be the width (i.e., thickness) of a minimumwidth infinite cylindrical shell (the region between two coaxial 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

