On geometric optimization with few violated constraints

ABSTRACT

We investigate the problem of finding the best solution satisfying all but k of the given constraints, for an abstract class of optimization problems introduced by Sharir and Welzl—the so-called LP-type problems. We give a general algorithm and discuss its efficient implementations for specific geometric problems. For instance, for the problem of computing the smallest circle enclosing all but k of the given n points in the plane, we obtain an O(nlogn+k3n&egr;) algorithm; this improves previous results for k small compared ton but moderately growing.We also establish some results concerning general properties of LP-type problems.

REFERENCES

• ACE+91: Boris Aronov , Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete & Computational Geometry, v.6 n.5, p.435-442, 1991 [doi>10.1007/BF02574700]
• AdBMS94: Pankaj K. Agarwal , Mark de Berg , Jiří Matoušek , Otfried Schwarzkopf, Constructing levels in arrangements and higher order Voronoi diagrams, Proceedings of the tenth annual symposium on Computational geometry, p.67-75, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177521]
• AIKS91: Alok Aggarwal , Hiroshi Imai , Naoki Katoh , Subhash Suri, Finding k points with minimum diameter and related problems, Journal of Algorithms, v.12 n.1, p.38-56, March 1991 [doi>10.1016/0196-6774(91)90022-Q]
• AM91: K P Agarwal , Jiri Matousek, Dynamic Half-Space Range Reporting and Its Application, Duke University, Durham, NC, 1991
• Ame93: Nina Amenta, Helly theorems and generalized linear programming, Proceedings of the ninth annual symposium on Computational geometry, p.63-72, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161000]
• Cla87: K.L. Clarkson. New applications of random sampling in computational geometry. Discrete Comput. Geom., 2:195-222, 1987.
• Cla88: K.L. Clarkson. ALas Vegas algorithm for linear programming when the dimension is small. In Proc. ~9th Annu. IEEE Sympos. Found. Comput. Sci., pages 452-456, 1988.
• Cla92: K.L. Clarkson. A bound on local minima of arrangements that implies the upper bound theorem. Manuscript, 1992.
• CM93: Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
• CS89: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• CSY87: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• DE93: Tamal K. Dey , Herbert Edelsbrunner, Counting triangle crossings and halving planes, Proceedings of the ninth annual symposium on Computational geometry, p.270-273, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161148]
• DLSS93: Amitava Datta , Hans-Peter Lenhof , Christian Schwarz , Michiel H. M. Smid, Static and Dynamic Algorithms for k-Point Clustering Problems, Proceedings of the Third Workshop on Algorithms and Data Structures, p.265-276, August 11-13, 1993
• EC92: Ioannis Emiris , John Canny, An efficient approach to removing geometric degeneracies, Proceedings of the eighth annual symposium on Computational geometry, p.74-82, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142694]
• EE93: David Eppstein , Jeff Erickson, Iterated nearest neighbors and finding minimal polytypes, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.64-73, January 25-27, 1993, Austin, Texas, United States
• ELS93: A. Efrat, M. Lindenbaum, and M. Sharir. Finding maximally consistent sets of halfspaces. In Proc. 5th Canadian Con/erence on Computational Geometry, 1993.
• EM90: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• ERvK93: Hazel Everett , Jean-Marc Robert , Marc van Kreveld, An optimal algorithm for the (≤ k)-levels, with applications to separation and transversal problems, Proceedings of the ninth annual symposium on Computational geometry, p.38-46, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160994]
• ES93: J. Erickson and R. Seidel. Better lower bounds for detecting affine and spherical degeneracies. In Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 9$), 1993.
• ESZ93: Alon Efrat , Micha Sharir , Alon Ziv, Computing the Smallest k-Enclosing Circle and Related Problems, Proceedings of the Third Workshop on Algorithms and Data Structures, p.325-336, August 11-13, 1993
• Gär92: B. Girtner. A subexponential algorithm for abstract optimization problems. In Proc. 33rd IEEE Sympos. Found. Comput. Sci., 1992.
• GO93: A. Gajentaan and M. Overmars. n2-hard problems in computational geometry. Tech. Report RUU-CS-93-15, Utrecht University, 1993.
• Kal92: Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129759]
• Mat93a: Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
• Mat93b: J. Matou~ek. On enclosing k points by a circle. Manuscript, 1993.
• Meg83: N. Megiddo. The weighted Euclidean 1-center problem. Math. Oper. Res., 8(4):498-504, 1983.
• MSW92: Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142678]
• Mul91: Ketan Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete & Computational Geometry, v.6 n.4, p.307-338, 1991 [doi>10.1007/BF02574692]
• Mul93: Ketan Mulmuley, Dehn-Sommerville relations, upper bound theorem, and levels in arrangements, Proceedings of the ninth annual symposium on Computational geometry, p.240-246, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161141]
• OvL81: M.H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23:166-204, 1981.
• Sei94: R. Seidel. The nature and meaning of perturbations in geometric computing. Manuscript, 1994.
• SW92: 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
• Wel91: E. Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, LNCS 555 (New Results and New Trends in Computer Science), pages 359-370. Springer-Verlag, 1991.
• Yap90: Chee-Keng Yap, A geometric consistency theorem for a symbolic perturbation scheme, Journal of Computer and System Sciences, v.40 n.1, p.2-18, February 1990 [doi>10.1016/0022-0000(90)90016-E]

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Theory, Verification