Minimum Enclosing Balls: Matlab Code

Piyush Kumar , J.S.B.Mitchell and Alper Yildirim
Most recent version of the associated paper Most recent version of the associated talk Abstract We study the minimum enclosing ball (MEB) problem for sets of points or balls in high dimensions. Using techniques of second-order cone programming and ``core-sets'', we have developed approximation algorithms that perform well in practice, especially for very high dimensions, in addition to having provable guarantees. This paper also improves upon the previously known k-center clustering result (PTAS). Code Core Set Code SOCP Code You will also need to download SDPT3, version 3.0 and set it in your path in matlab before you can run the above code. Download both the files and save it in a directory that in your MATLAB path. A Test run for 1000 points in 3D can be done using the command: P = randn(3,1000); meb(P,1e-3); Recently we have also implemented k-center clustering PTAS for fixed dimensions. Here are some outputs :- (epsilon = 0.01)

Piyush Kumar , J.S.B.Mitchell and Alper Yildirim

Most recent version of the associated paper

Most recent version of the associated talk

Abstract

We study the minimum enclosing ball (MEB) problem for sets of points or balls in high dimensions. Using techniques of second-order cone programming and ``core-sets'', we have developed approximation algorithms that perform well in practice, especially for very high dimensions, in addition to having provable guarantees. This paper also improves upon the previously known k-center clustering result (PTAS).

Code

You will also need to download SDPT3, version 3.0 and set it in your path in matlab before you can run the above code. Download both the files and save it in a directory that in your MATLAB path. A Test run for 1000 points in 3D can be done using the command:

P = randn(3,1000);
meb(P,1e-3);

Recently we have also implemented k-center clustering PTAS for fixed dimensions. Here are some outputs :- (epsilon = 0.01)