**Up:** *Directory of Computational Geometry Software*

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*

*The Geometry Center Home Page*
Comments to: nina@geom.umn.edu

Created: May 31 1995 ---
Last modified: Thu Jun 1 14:29:20 1995