A class of convex programs with applications to computational geometry
Martin Dyer · 1992
We consider the solution of convex programs in a small number of variables but large number of constraints, where all but a small number of the constraints are linear. We develop a general framework for obtaining algorithms for these problems which run in time linear in the number of constraints. We give an application to computing minimum spanning ellipsoids in fixed dimension.