Up: Directory of Computational Geometry Software

Linear programming, smallest enclosing ball and center point

The computational geometry flavored LP program here solves LP-type (aka Generalized Linear Programming) problems, which are not necessarily linear. For traditional LP programs, which can probably handle much larger problems more robustly, see the

linprog

 Low-dimensional linear programming using Seidel's randomized incremental algorithm. Also handles rational objective functions, so with some cleverness you can get polytope separation distance, linear programming on a sphere, ect. C source code.

By Mike Hohmeyer, then at U.C. Berkeley.
Available by ftp from ICEMCFD, Mike's company.

ball

 Finds the smallest ball enclosing a family of balls, in arbitrary dimension, using the randomized incremental method. In C++, calling some Numerical Recipes routines.

Take a look at the Web page for more details and pointers to the code.

By David White, U.C.S.D.

Approximate center point

 Finds an approximate center point by iteratively finding Radon points, using an algorithm due to Clarkson, Eppstein, Miller, Sturtivant and Teng. A little C program.
There is more information, pointers to the paper and the code, and a really nice picture on the Web page .

Code by Ken Clarkson, of Bell Labs.

Up: Directory of Computational Geometry Software
[HOME] The Geometry Center Home Page

Comments to: nina@geom.umn.edu
Created: May 31 1995 --- Last modified: Thu Jun 1 14:29:20 1995