The Number of Cylindrical Shells

Given a set P of n points in three dimensions,a cylindrical shell (or zone cylinder) is formed by twocircular cylinders with the same axis such that all pointsof P are between the two cylinders.We prove that the number of cylindrical shells enclosing P passing through combinatorially different subsets of Phas size (n ³) andO(n ⁴) (the previously known bound was O(n ⁵)).As a consequence,the minimum enclosing shell can be found in O(n ⁴) time.