Bo Tian

Bouncing Bubble: a Fast Algorithm for Minimal Enclosing Ball Problem Bo Tian

Scholarly Essay from the year 2012 in the subject Computer Science - Theory, grade: -, -, language: English, abstract: In this paper, a new algorithm for solving MEB problem is proposed based on new understandings on the geometry property of minimal enclosing ball problem. A substitution of Ritter's algorithm is proposed to get approximate results with higher precision, and a 1+? approximation algorithm is presented to get approximation with specified precision within much less time comparing with present algorithms. With the new 1+? approximation algorithm , A large case d=2048, n=128k, ?=10-6 can be solved within 4 minutes, which has not been done with previous solvers.