Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope

ABSTRACT

In this paper, we consider the problem of computing a maximum inscribed sphere inside a high dimensional polytope formed by a set of halfspaces (or linear constraints) and with bounded aspect ratio, and present an efficient algorithm for computing a (1−ε)-approximation of the sphere. More specifically, given any aspect-ratio-bounded polytope P defined by n d-dimensional halfspaces, an interior point O of P, and a constant ε>0, our algorithm computes in O(nd/ε³) time a sphere inside P with a radius no less than (1−ε)R_opt, where R_opt is the radius of a maximum inscribed sphere of P. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd [13].

REFERENCES

• 1: P.K. Agarwal, S. Har-Peled, and K. R. Varadarajan, "Geometric Approximation via Coresets," Survey, 2005.
• 2: Kurt M. Anstreicher, Improved Complexity for Maximum Volume Inscribed Ellipsoids, SIAM Journal on Optimization, v.13 n.2, p.309-320, 2002 [doi>10.1137/S1052623401390902]
• 3: A.Barvinok, G.Blekherman, "Convex Geometry of Orbits", manuscript, 2003.
• 4: Mihai Bâdoiu , Kenneth L. Clarkson, Smaller core-sets for balls, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 6: J.Elzinga, T.Moore, "A central cutting plane algorithm for the convex programming problem", Math. Programming, 8, pp. 134--145, 1975.
• 7: M.Grotschel, L.Lovasz, and A.Schrijver, "Geometric Algorithms and Combinatorial Optimization", Springer, New York, 1988.
• 8: C. C. Gonzaga, An algorithm for solving linear programming programs in 0(n0S3L) operations, on Progress in Mathematical Programming: Interior-Point and Related Methods, p.1-28, September 1989, Pacific Grove, California, United States
• 9: S.Har-Peled, K.Varadarajan, "Projective clustering in high dimensions using core-sets", Proc.18th Annu.ACM Sympos. Theory Comput., 2004.
• 10: Sariel Har-Peled , Kasturi R. Varadarajan, High-Dimensional Shape Fitting in Linear Time, Discrete & Computational Geometry, v.32 n.2, p.269-288, July 2004 [doi>10.1007/s00454-004-1118-2]
• 11: Leonid G. Khachiyan, Rounding of polytopes in the real number model of computation, Mathematics of Operations Research, v.21 n.2, p.307-320, May 1996
• 12: P.Kumar, J.Mitchell, A.Yildirim, "Computing Core-Sets and Approximate Smallest Enclosing Hyperspheres in High Dimensions", manuscript, 2002.
• 13: Leonid G. Khachiyan , Michael J. Todd, On the complexity of approximating the maximal inscribed ellipsoid for a polytope, Mathematical Programming: Series A and B, v.61 n.2, p.137-159, Sept. 3, 1993
• 14: P.Kumar, A.Yildirim, "Minimum volume enclosing ellipsoids and core sets, Journal of Optimization Theory and Applications", 2005. To Appear.
• 15: G.Nemhauser, W.Widhelm, "A modified linear program for columnar methods in mathematical programming", Operation Research, 19, pp. 1051--1060, 1971.
• 16: R.Panigrahy, "Minimum enclosing polytope in high dimensions", manuscript, 2004.
• 17: Yinyu Ye, Interior point algorithms: theory and analysis, John Wiley & Sons, Inc., New York, NY, 1997
• 18: Yin Zhang , Liyan Gao, On Numerical Solution of the Maximum Volume Ellipsoid Problem, SIAM Journal on Optimization, v.14 n.1, p.53-76, 2003 [doi>10.1137/S1052623401397230]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
approximation, chebyshev center, core-set, maximum inscribed sphere, polytope