Faculty of Engineering and Natural Sciences
Efficient Algorithms for Large-Scale Minimum Enclosing Ball
Emre Alper Yıldırım
Department of Industrial Engineering
We discuss simple and efficient algorithms for the approximate computation of the minimum enclosing ball of a given finite but large-scale set of points in a high-dimensional space. Our algorithms are iterative in nature and use only first-order information. The algorithms properly exploit the underlying geometric structure of the problem and have a nice geometric interpretation. We establish the existence of a small subset of points whose minimum enclosing ball provides a good approximation to that of the original input set. We also discuss ways to enhance the performances of our algorithms by identifying and eliminating interior points. We establish that our algorithms can be extended to the approximate computation of the minimum enclosing ball of much more general input sets without sacrificing most of their desirable features.
E. Alper Yildirim earned his B.S. degree in Industrial Engineering at
University in 1997 and his M.S. and Ph.D. degrees in Operations Research at
University in 2000 and 2001, respecively. He worked as an Assistant Professor at the Department of Applied Mathematics and Statistics at
University between 2001 and 2005. He then joined the Department of Industrial Engineering at
University, where he currently works as an Associate Professor. His research interests are mainly in mathematical programming including theory, algorithms, and applications.
Wednesday, 28 January 2009, 13:40-14:40,