A class of convex programs with applications to computational geometry

ABSTRACT

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.

REFERENCES

• 1: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 2: K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
• 3: K. L. Clarkson, "ALas Vegas algorithm for linear programming when the dimension is small", Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988, pp 452-456.
• 4: D. P. Dobkin and D. G. Kirkpatrick, "A linear algorithm for determining the separation of convex polyhedra", Journal of Algorithms 6 (1985), 381-393.
• 5: M. E. Dyer, ':On a multidimcn~ionM ~c~rch procedure and its application to the Euclidean onecentre problem", SIAM Journal on Computing 13 (1984), 31-45.
• 6: M. GrStschel, L. Lovg~z and A. Schrijvcr, Geometric algorithms and combinatorial optimization, Springer, Berlin, 1988.
• 7: N. Jacobson, Basic algebra I (Second edition), Freeman, New York, 1985.
• 8: N. Megiddo, "Linear programming in linear time when the dimension is fixed", SIAM Journal on Computing 12 (1983), 759-776.
• 9: N. Megiddo, On the ball spanned by balls, Discrete & Computational Geometry, v.4 n.6, p.605-610, Sep. 1989 [doi>10.1007/BF02187750]
• 10: M. Minoux, Mathematical programming-ih~o~?I and algorithms, Wiley, Chichester, 1986.
• 11: Mark J. Post, Minimum spanning ellipsoids, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.108-116, December 1984 [doi>10.1145/800057.808672]
• 12: J. Renegar, "A faster PSPACE algorithm for deciding the existential theory of the reals", Proc. ~gth IEEE Symposium on Foundations of Computer Science, 1988, pp 291-295.
• 13: Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992
• 14: E. Welzl, "Smallest enclosing disks (balls and ellipsoids)'', to appear in New Results and New Trends in Computer Science, (H. Maurer, Ed.), Lecture Notes in Computer Science, 1991.

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms