Analytic Center of Convex Polytope

Solution 1:

I think your best bet is to formulate your problem as a linear program that finds the Chebyshev center of a polyhedron.

By finding the Chebyshev center of the polyhedron, you try to find the largest hyper-sphere that fits inside the convex hull of the vertices. And, the center of this hyper-sphere can be defined as the center of your polytope.

Take a look at slide 4-19 here:

http://stanford.edu/class/ee364a/lectures/problems.pdf

This problem is surprisingly interesting, because it can be converted to a simple linear program, which can be efficiently solved.

Note that this solution is not necessarily unique, and in particular if the polytope is "thin", then "the center" will be less meaningful. (I.e., you may want to add extra constraints to the optimization program, or change the objective to account for that as well.)

I hope this helps.