On geometric optimization with few violated constraints. (English) Zbl 0844.90071
Summary: 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(n \log n + k^3 n^\varepsilon)\) algorithm; this improves previous results for \(k\) small compared with \(n\) but moderately growing. We also establish some results concerning general properties of LP-type problems.
MSC:
| 90C27 | Combinatorial optimization |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | P. Agarwal, M. de Berg, J. Matoušek, and O. Schwarzkopf. Constructing levels in arrangements and higher-order Voronoi diagrams.Proc. 10th Ann. ACM Symp. on Computational Geometry, pp. 67-75, 1994. · Zbl 0913.65145 |
| [2] | P. K. Agarwal and J. Matoušek. Dynamic half-space range reporting and its applications.Algorithmica, 13:325-345, 1995. · Zbl 0827.68037 · doi:10.1007/BF01293483 |
| [3] | A. Aggarwal, H. Imai, N. Katoh, and S. Suri. Findingk points with minimum diameter and related problems.J. Algorithms, 12:38-56, 1991. · Zbl 0715.68082 · doi:10.1016/0196-6774(91)90022-Q |
| [4] | N. Amenta. Helly theorems and generalized linear programming.Discrete Comput. Geom., 12:241-261, 1994. · Zbl 0819.90056 · doi:10.1007/BF02574379 |
| [5] | B. Aronov, B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and R. Wenger. Points and triangles in the plane and halving planes in space.Discrete Comput. Geom., 6:435-442, 1991. · Zbl 0764.68057 · doi:10.1007/BF02574700 |
| [6] | B. Chazelle and J. Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension.Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 281-290, 1993. · Zbl 0808.90090 |
| [7] | K. L. Clarkson. New applications of random sampling in computational geometry.Discrete Comput. Geom., 2:195-222, 1987. · Zbl 0615.68037 · doi:10.1007/BF02187879 |
| [8] | K. L. Clarkson. A Las Vegas algorithm for linear programming when the dimension is small.Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science, pp. 452-456, 1988. |
| [9] | K. L. Clarkson. A bound on local minima of arrangements that implies the upper bound theorem. Manuscript, 1992. · Zbl 0792.52006 |
| [10] | K. L. Clarkson and P. W. Shor. Application of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387-421, 1989. · Zbl 0681.68060 · doi:10.1007/BF02187740 |
| [11] | R. Cole, M. Sharir, and C. K. Yap. Onk-hulls and related problems.SIAM J. Comput., 16:61-77, 1987. · Zbl 0637.68074 · doi:10.1137/0216005 |
| [12] | Datta, A.; Lenhof, H.-P.; Schwarz, C.; Smid, M., Static and dynamic algorithms fork-point clustering problems, No. vol. 709, 265-276 (1993), Berlin · Zbl 1504.68251 · doi:10.1007/3-540-57155-8_254 |
| [13] | T. Dey and H. Edelsbrunner: Counting triangle crossings and halving planes.Discrete Comput. Geom., 12:281-289, 1994. · Zbl 0819.68135 · doi:10.1007/BF02574381 |
| [14] | H. Edelsbrunner and E. P. Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.ACM Trans. Graphics 9:66-104, 1990. · Zbl 0732.68099 · doi:10.1145/77635.77639 |
| [15] | A. Efrat, M. Lindenbaum, and M. Sharir, Finding maximally consistent sets of halfspaces.Proc. 5th Canad. Conf. on Computational Geometry, pp. 432-436, Waterloo, Ontario, 1993. |
| [16] | Efrat, A.; Sharir, M.; Ziv, A., Computing the smallestk-enclosing circle and related problems, No. vol. 709, 325-336 (1993), Berlin · Zbl 1504.68253 · doi:10.1007/3-540-57155-8_259 |
| [17] | I. Emiris and J. Canny. An efficient approach to removing geometric degeneracies.Proc. 8th Ann. ACM Symp. on Computational Geometry, pp. 74-82, 1992. |
| [18] | D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes.Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 64-73, 1993. · Zbl 0801.68162 |
| [19] | H. Everett, J.-M. Robert, and M. van Kreveld. An optimal algorithm for the (≤k)-levels, with applications to separation and transversal problems.Proc. 9th Ann. ACM Symp. on Computational Geometry, pp. 38-46, 1993. |
| [20] | A. Gajentaan and M. H. Overmars.n2-hard problems in computational geometry. Report RUU-CS-93-15, Department of Computer Science, Utrecht University, Utrecht, April 1993. |
| [21] | B. Gärtner. A subexponential algorithm for abstract optimization problems.Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, pp. 464-472, 1992. · Zbl 0977.68874 |
| [22] | D. S. Johnson and F. P. Preparata. The densest hemisphere problem.Theoret. Comput. Sci., 6:93-107, 1978. · Zbl 0368.68053 · doi:10.1016/0304-3975(78)90006-3 |
| [23] | G. Kalai, A subexponential randomized simplex algorithm.Proc. 24th Ann. ACM Symp. on Theory of Computing, pp. 475-482, 1992. |
| [24] | J. Matoušek, Linear optimization queries.J. Algorithms, 14:432-448, 1993. The results combined with the results of O. Schwarzkopf also appear inProc. 8th ACM Symp. on Computational Geometry, pp. 16-25, 1992. · Zbl 0779.68089 · doi:10.1006/jagm.1993.1023 |
| [25] | J. Matoušek, On enclosingk points by a circle.Inform. Process. Lett., 53:217-221, 1995. · Zbl 0875.68895 · doi:10.1016/0020-0190(94)00190-A |
| [26] | J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming.Proc. 8th Ann. ACM Symp. on Computational Geometry, pp. 1-8, 1992. Also to appear inAlgorithmica. · Zbl 0857.68119 |
| [27] | N. Megiddo. The weighted Euclidean 1-center problem.Math. Oper. Res., 8(4):498-504, 1983. · Zbl 0533.90030 · doi:10.1287/moor.8.4.498 |
| [28] | K. Mulmuley. On levels in arrangements and Voronoi diagrams.Discrete Comput. Geom., 6:307-338, 1991. · Zbl 0727.68129 · doi:10.1007/BF02574692 |
| [29] | K. Mulmuley. Dehn-Sommerville relations, upper bound theorem, and levels in arrangements.Proc. 9th Ann. ACM Sump. on Computational Geometry, pp. 240-246, 1993. |
| [30] | M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane.J. Comput. System Sci., 23:166-204, 1981. · Zbl 0474.68082 · doi:10.1016/0022-0000(81)90012-X |
| [31] | Seidel, R., The nature and meaning of perturbations in geometric computing (1994), Berlin · Zbl 0892.68100 |
| [32] | Sharir, M.; Welzl, E., A combinatorial bound for linear programming and related problems, No. vol. 577, 569-579 (1992), Berlin · Zbl 1494.68276 |
| [33] | C. K. Yap. A geometric consistency theorem for a symbolic perturbation scheme.J. Comput. System Sci. 40:2-18, 1990. · Zbl 0705.68056 · doi:10.1016/0022-0000(90)90016-E |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
