Exact and approximation algorithms for minimum-width cylindrical shells
Pankaj K. Agarwal, Boris S. Aronov, Micha Sharir · 2000
Let S be a set of n points in R 3 . 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 5 )-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+ffi )-time algorithm, for any ffi ? 0, that computes a cylindrical shell of width at most 26(1 + 1=n 4=9 )! containing S. 1 Introduction Given a line ` in R 3 and two real numbers 0 r R, the cylindrical shell \\Sigma(`; r; R) is the closed region lying between the two co-axial cylinders of radii r and R with ` as their axis, i.e., \\Sigma(`; r; R) = fp 2 R 3 j r d(p; `) Rg; where d(p; `) is the Euclidean distance between point p and line `. The width of \\Sigma(`; r; R) is R\\Gammar. Let S be a set of n points in R 3 . How well S fits a cylindrical surface can be measured by computing a cylindrical surface C = C(...