Smallest enclosing cylinders

This paper addresses the complexity of computing the smallest-radius infini te cylinder that encloses an input set of n points in 3-space. We show that the problem can be solved in time O(n(4) log(O(1)) n) in an algebraic comp lexity model. We also achieve a time of O(n(4)L . mu(L)) in st bit complexi ty model where L is the maximum bit size of input numbers and mu(L) is the complexity of multiplying two L bit integers. These and several other results highlight a general linearization technique which transforms nonlinear problems into some higher-dimensional but linea r problems. The; technique is reminiscent of the use of Plucker coordinates , and is used here in conjunction with Megiddo's parametric searching. We further report on experimental work comparing the practicality of an exa ct with that of a numerical strategy.