{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T15:04:48Z","timestamp":1773241488932,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete &amp; Computational Geometry"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf02570713","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T04:22:00Z","timestamp":1177734120000},"page":"365-384","source":"Crossref","is-referenced-by-count":84,"title":["On geometric optimization with few violated constraints"],"prefix":"10.1007","volume":"14","author":[{"given":"J.","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1995,12,1]]},"reference":[{"key":"BF02570713_CR1","doi-asserted-by":"crossref","unstructured":"P. Agarwal, M. de Berg, J. Matou\u0161ek, and O. Schwarzkopf. Constructing levels in arrangements and higher-order Voronoi diagrams.Proc. 10th Ann. ACM Symp. on Computational Geometry, pp. 67\u201375, 1994.","DOI":"10.1145\/177424.177521"},{"key":"BF02570713_CR2","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"P. K. Agarwal","year":"1995","unstructured":"P. K. Agarwal and J. Matou\u0161ek. Dynamic half-space range reporting and its applications.Algorithmica, 13:325\u2013345, 1995.","journal-title":"Algorithmica"},{"key":"BF02570713_CR3","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/0196-6774(91)90022-Q","volume":"12","author":"A. Aggarwal","year":"1991","unstructured":"A. Aggarwal, H. Imai, N. Katoh, and S. Suri. Findingk points with minimum diameter and related problems.J. Algorithms, 12:38\u201356, 1991.","journal-title":"J. Algorithms"},{"key":"BF02570713_CR4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02574379","volume":"12","author":"N. Amenta","year":"1994","unstructured":"N. Amenta. Helly theorems and generalized linear programming.Discrete Comput. Geom., 12:241\u2013261, 1994.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570713_CR5","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/BF02574700","volume":"6","author":"B. Aronov","year":"1991","unstructured":"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\u2013442, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570713_CR6","unstructured":"B. Chazelle and J. Matou\u0161ek. On linear-time deterministic algorithms for optimization problems in fixed dimension.Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 281\u2013290, 1993."},{"key":"BF02570713_CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K. L. Clarkson. New applications of random sampling in computational geometry.Discrete Comput. Geom., 2:195\u2013222, 1987.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570713_CR8","doi-asserted-by":"crossref","unstructured":"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\u2013456, 1988.","DOI":"10.1109\/SFCS.1988.21961"},{"key":"BF02570713_CR9","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson. A bound on local minima of arrangements that implies the upper bound theorem. Manuscript, 1992.","DOI":"10.1007\/BF02573988"},{"key":"BF02570713_CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor. Application of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387\u2013421, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570713_CR11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1137\/0216005","volume":"16","author":"R. Cole","year":"1987","unstructured":"R. Cole, M. Sharir, and C. K. Yap. Onk-hulls and related problems.SIAM J. Comput., 16:61\u201377, 1987.","journal-title":"SIAM J. Comput."},{"key":"BF02570713_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/3-540-57155-8_254","volume-title":"Proc. 3rd Workshop on Algorithms and Data Structures","author":"A. Datta","year":"1993","unstructured":"A. Datta, H.-P. Lenhof, C. Schwarz, and M. Smid. Static and dynamic algorithms fork-point clustering problems.Proc. 3rd Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 709, pp. 265\u2013276. Springer-Verlag, Berlin, 1993."},{"key":"BF02570713_CR13","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02574381","volume":"12","author":"T. Dey","year":"1994","unstructured":"T. Dey and H. Edelsbrunner: Counting triangle crossings and halving planes.Discrete Comput. Geom., 12:281\u2013289, 1994.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570713_CR14","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner and E. P. M\u00fccke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.ACM Trans. Graphics 9:66\u2013104, 1990.","journal-title":"ACM Trans. Graphics"},{"key":"BF02570713_CR15","unstructured":"A. Efrat, M. Lindenbaum, and M. Sharir, Finding maximally consistent sets of halfspaces.Proc. 5th Canad. Conf. on Computational Geometry, pp. 432\u2013436, Waterloo, Ontario, 1993."},{"key":"BF02570713_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/3-540-57155-8_259","volume-title":"Proc. 3rd Workshop on Algorithms and Data Structures","author":"A. Efrat","year":"1993","unstructured":"A. Efrat, M. Sharir, and A. Ziv. Computing the smallestk-enclosing circle and related problems.Proc. 3rd Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 709, pp. 325\u2013336. Springer-Verlag, Berlin, 1993."},{"key":"BF02570713_CR17","doi-asserted-by":"crossref","unstructured":"I. Emiris and J. Canny. An efficient approach to removing geometric degeneracies.Proc. 8th Ann. ACM Symp. on Computational Geometry, pp. 74\u201382, 1992.","DOI":"10.1145\/142675.142694"},{"key":"BF02570713_CR18","unstructured":"D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes.Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 64\u201373, 1993."},{"key":"BF02570713_CR19","doi-asserted-by":"crossref","unstructured":"H. Everett, J.-M. Robert, and M. van Kreveld. An optimal algorithm for the (\u2264k)-levels, with applications to separation and transversal problems.Proc. 9th Ann. ACM Symp. on Computational Geometry, pp. 38\u201346, 1993.","DOI":"10.1145\/160985.160994"},{"key":"BF02570713_CR20","series-title":"Report RUU-CS-93-15","volume-title":"n 2-hard problems in computational geometry","author":"A. Gajentaan","year":"1993","unstructured":"A. Gajentaan and M. H. Overmars.n 2-hard problems in computational geometry. Report RUU-CS-93-15, Department of Computer Science, Utrecht University, Utrecht, April 1993."},{"key":"BF02570713_CR21","doi-asserted-by":"crossref","unstructured":"B. G\u00e4rtner. A subexponential algorithm for abstract optimization problems.Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, pp. 464\u2013472, 1992.","DOI":"10.1109\/SFCS.1992.267805"},{"key":"BF02570713_CR22","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","volume":"6","author":"D. S. Johnson","year":"1978","unstructured":"D. S. Johnson and F. P. Preparata. The densest hemisphere problem.Theoret. Comput. Sci., 6:93\u2013107, 1978.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02570713_CR23","doi-asserted-by":"crossref","unstructured":"G. Kalai, A subexponential randomized simplex algorithm.Proc. 24th Ann. ACM Symp. on Theory of Computing, pp. 475\u2013482, 1992.","DOI":"10.1145\/129712.129759"},{"key":"BF02570713_CR24","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1006\/jagm.1993.1023","volume":"14","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek, Linear optimization queries.J. Algorithms, 14:432\u2013448, 1993. The results combined with the results of O. Schwarzkopf also appear inProc. 8th ACM Symp. on Computational Geometry, pp. 16\u201325, 1992.","journal-title":"J. Algorithms"},{"key":"BF02570713_CR25","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0020-0190(94)00190-A","volume":"53","author":"J. Matou\u0161ek","year":"1995","unstructured":"J. Matou\u0161ek, On enclosingk points by a circle.Inform. Process. Lett., 53:217\u2013221, 1995.","journal-title":"Inform. Process. Lett."},{"key":"BF02570713_CR26","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming.Proc. 8th Ann. ACM Symp. on Computational Geometry, pp. 1\u20138, 1992. Also to appear inAlgorithmica.","DOI":"10.1145\/142675.142678"},{"issue":"4","key":"BF02570713_CR27","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/moor.8.4.498","volume":"8","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. The weighted Euclidean 1-center problem.Math. Oper. Res., 8(4):498\u2013504, 1983.","journal-title":"Math. Oper. Res."},{"key":"BF02570713_CR28","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K. Mulmuley","year":"1991","unstructured":"K. Mulmuley. On levels in arrangements and Voronoi diagrams.Discrete Comput. Geom., 6:307\u2013338, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570713_CR29","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Dehn-Sommerville relations, upper bound theorem, and levels in arrangements.Proc. 9th Ann. ACM Sump. on Computational Geometry, pp. 240\u2013246, 1993.","DOI":"10.1145\/160985.161141"},{"key":"BF02570713_CR30","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. H. Overmars","year":"1981","unstructured":"M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane.J. Comput. System Sci., 23:166\u2013204, 1981.","journal-title":"J. Comput. System Sci."},{"key":"BF02570713_CR31","series-title":"Lecture Notes in Computer Science","volume-title":"Proc. 11th Symp. on Theoretical Aspects of Computer Science (STACS)","author":"R. Seidel","year":"1994","unstructured":"R. Seidel. The nature and meaning of perturbations in geometric computing.Proc. 11th Symp. on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1994."},{"key":"BF02570713_CR32","series-title":"Lecture Notes in Computer Science","first-page":"569","volume-title":"Proc. 1992 Symp. on Theoretical Aspects of Computer Science","author":"M. Sharir","year":"1992","unstructured":"M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems.Proc. 1992 Symp. on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 577, pp 569\u2013579. Springer-Verlag, Berlin, 1992."},{"key":"BF02570713_CR33","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0022-0000(90)90016-E","volume":"40","author":"C. K. Yap","year":"1990","unstructured":"C. K. Yap. A geometric consistency theorem for a symbolic perturbation scheme.J. Comput. System Sci. 40:2\u201318, 1990.","journal-title":"J. Comput. System Sci."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570713.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02570713\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T15:59:43Z","timestamp":1558195183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02570713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF02570713"],"URL":"https:\/\/doi.org\/10.1007\/bf02570713","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}