Up: Directory of Computational Geometry Software

Linear programming, smallest enclosing ball and center point

The computational geometry flavored LP programs here solves LP-type (aka Generalized Linear Programming) problems, which are not necessarily linear. They might also be faster for low dimensional problems with many constraints. For traditional LP programs, which can probably handle much larger problems more robustly, see the Linear programming FAQ.

Finding the smallest ball containing a family of balls is another LP-type problem. Very nice for manipulating objects surrounded by bounding balls.

A center point is kind of like a d-dimensional median; any hyperplane through a center point cuts the input point set into two roughly equal pieces. The truely hard-core will realize that center points belong on this page because the dumb way to find one is by linear programming.

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.

lp

 Simple LP programs using Clarkson's algorithm or Seidel's algorithm, in C. Will probably require some hacking on your part.

See the Web page for more info on the nifty algorithm and a link to the code.

By Ken Clarkson, Bell Labs.

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