{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T03:25:17Z","timestamp":1764645917706,"version":"3.33.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,3,5]],"date-time":"2008-03-05T00:00:00Z","timestamp":1204675200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2008,9]]},"DOI":"10.1007\/s11222-008-9054-2","type":"journal-article","created":{"date-parts":[[2008,3,4]],"date-time":"2008-03-04T20:26:28Z","timestamp":1204662388000},"page":"259-266","source":"Crossref","is-referenced-by-count":24,"title":["Output-sensitive algorithms for Tukey depth and related problems"],"prefix":"10.1007","volume":"18","author":[{"given":"David","family":"Bremner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,3,5]]},"reference":[{"key":"9054_CR1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E. Amaldi","year":"1995","unstructured":"Amaldi, E., Kann, V.: The complexity and approximability of finding maximum feasible subsystems of linear relations. Theor. Comput. Sci. 147, 181\u2013210 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"1\/2","key":"9054_CR2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/S0304-3975(98)00003-6","volume":"205","author":"P.A. Beling","year":"1998","unstructured":"Beling, P.A., Megiddo, N.: Using fast matrix multiplication to find basic solutions. Theor. Comput. Sci. 205(1\/2), 307\u2013316 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9054_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees (preliminary report). In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC\u201983), pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"9054_CR4","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 617\u2013626 (2002)","DOI":"10.1109\/SFCS.2002.1181985"},{"key":"9054_CR5","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 423\u2013429 (2004)"},{"key":"9054_CR6","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1137\/S0097539703439404","volume":"34","author":"T.M. Chan","year":"2005","unstructured":"Chan, T.M.: Low-dimensional linear programming with violations. SIAM J. Comput. 34, 879\u2013893 (2005)","journal-title":"SIAM J. Comput."},{"key":"9054_CR7","series-title":"Series of Books in the Mathematical Sciences","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear Programming. Series of Books in the Mathematical Sciences. Freeman, New York (1983)"},{"key":"9054_CR8","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42, 488\u2013499 (1995)","journal-title":"J. ACM"},{"key":"9054_CR9","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill, New York (2001)","edition":"2"},{"key":"9054_CR10","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"9054_CR11","doi-asserted-by":"crossref","unstructured":"Dyer, M.E.: Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput., 31\u201345 (1984)","DOI":"10.1137\/0213003"},{"key":"9054_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4613-9617-8_1","volume-title":"Progress in Mathematical Programming","author":"C.C. Gonzaga","year":"1989","unstructured":"Gonzaga, C.C.: An algorithm for solving linear programming problems in O(n 3 L) operations. In: Progress in Mathematical Programming, Pacific Grove, CA, 1987, pp. 1\u201328. Springer, New York (1989)"},{"key":"9054_CR13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","volume":"6","author":"D.S. Johnson","year":"1978","unstructured":"Johnson, D.S., Preparata, F.P.: The densest hemisphere problem. Theor. Comput. Sci. 6, 93\u2013107 (1978)","journal-title":"Theor. Comput. Sci."},{"key":"9054_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-36494-3_6","volume-title":"Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science","author":"S. Langerman","year":"2003","unstructured":"Langerman, S., Steiger, W.: Optimization in arrangements. In: Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2607, pp. 50\u201361. Springer, Berlin (2003)"},{"key":"9054_CR15","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1090\/dimacs\/006\/14","volume-title":"Computational Geometry: Papers from the Special Year","author":"J. Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Computing the center of planar point sets. In: Goodman, J.E., Pollack, R., Steiger, W. (eds.) Computational Geometry: Papers from the Special Year, pp. 221\u2013230. AMS, Providence (1991)"},{"key":"9054_CR16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. Theory Appl. 2, 169\u2013186 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9054_CR17","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02570713","volume":"14","author":"J. Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: On geometric optimization with few violated constraints. Discrete Comput. Geom. 14, 365\u2013384 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9054_CR18","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear time algorithms for linear programming in \u211d3 and related problems. SIAM J. Comput. 12, 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"key":"9054_CR19","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31, 114\u2013127 (1984)","journal-title":"J. ACM"},{"issue":"1","key":"9054_CR20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1287\/ijoc.3.1.63","volume":"3","author":"N. Megiddo","year":"1991","unstructured":"Megiddo, N.: On finding primal- and dual-optimal bases. ORSA J. Comput. 3(1), 63\u201365 (1991)","journal-title":"ORSA J. Comput."},{"key":"9054_CR21","volume-title":"Computational Geometry: An Introduction through Randomized Algorithms","author":"K. Mulmuley","year":"1998","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction through Randomized Algorithms. Prentice-Hall, Englewood Cliffs (1998)"},{"key":"9054_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"9054_CR23","doi-asserted-by":"crossref","unstructured":"Ramos, E.: On range reporting, ray shooting, and k-level construction. In: Proceedings of the 15th ACM Symposium on Computational Geometry (SoCG 1999), pp. 390\u2013399 (1999)","DOI":"10.1145\/304893.304993"},{"issue":"1","key":"9054_CR24","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01580724","volume":"40","author":"J. Renegar","year":"1988","unstructured":"Renegar, J.: A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Math. Program. (Ser. A) 40(1), 59\u201393 (1988)","journal-title":"Math. Program. (Ser. A)"},{"key":"9054_CR25","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BFb0083592","volume-title":"Optimization","author":"C. Roos","year":"1989","unstructured":"Roos, C.: An O(n 3 L) approximate center method for linear programming. In: Optimization, Varetz, 1988. Lecture Notes in Mathematics, vol. 1405, pp. 147\u2013158. Springer, Berlin (1989)"},{"issue":"3","key":"9054_CR26","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01586056","volume":"54","author":"C. Roos","year":"1992","unstructured":"Roos, C., Vial, J.-Ph.: A polynomial method of approximate centers for linear programming. Math. Program. Ser. A 54(3), 295\u2013305 (1992)","journal-title":"Math. Program. Ser. A"},{"key":"9054_CR27","first-page":"827","volume":"8","author":"P.J. Rousseeuw","year":"1998","unstructured":"Rousseeuw, P.J., Ruts, I.: Constructing the bivariate Tukey median. Stat. Sinica. 8, 827\u2013839 (1998)","journal-title":"Stat. Sinica."},{"key":"9054_CR28","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0167-9473(96)00027-8","volume":"23","author":"I. Ruts","year":"1996","unstructured":"Ruts, I., Rousseeuw, P.J.: Computing depth contours of bivariate point clouds. Comput. Stat. Data Anal. 23, 153\u2013168 (1996)","journal-title":"Comput. Stat. Data Anal."},{"key":"9054_CR29","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"Seidel, R.: Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom. 6, 423\u2013434 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"9054_CR30","series-title":"Lecture Notes in Computer Science","first-page":"569","volume-title":"Proceedings of the 9th Symposium on Theoretical Aspects of Computer Science","author":"M. Sharir","year":"1992","unstructured":"Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: Proceedings of the 9th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 5777, pp. 569\u2013579. Springer, Berlin (1992)"},{"key":"9054_CR31","doi-asserted-by":"crossref","first-page":"263","DOI":"10.2307\/1403809","volume":"58","author":"C.G. Small","year":"1990","unstructured":"Small, C.G.: A survey on multidimensional medians. Int. Stat. Rev. 58, 263\u2013277 (1990)","journal-title":"Int. Stat. Rev."},{"key":"9054_CR32","unstructured":"Tukey, J.W.: Mathematics and the picturing of data. In: Proceedings of the International Congress of Mathematicians, vol.\u00a02, pp. 523\u2013531 (1975)"},{"issue":"2","key":"9054_CR33","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01580859","volume":"47","author":"P.M. Vaidya","year":"1990","unstructured":"Vaidya, P.M.: An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations. Math. Program. Ser. A 47(2), 175\u2013201 (1990)","journal-title":"Math. Program. Ser. A"},{"key":"9054_CR34","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/BF02206830","volume":"62","author":"S.A. Vavasis","year":"1996","unstructured":"Vavasis, S.A., Ye, Y.: Identifying an optimal basis in linear programming. Interior point methods in mathematical programming. Ann. Oper. Res. 62, 565\u2013572 (1996)","journal-title":"Ann. Oper. Res."}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-008-9054-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11222-008-9054-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-008-9054-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T22:23:06Z","timestamp":1738102986000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11222-008-9054-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,5]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["9054"],"URL":"https:\/\/doi.org\/10.1007\/s11222-008-9054-2","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"type":"print","value":"0960-3174"},{"type":"electronic","value":"1573-1375"}],"subject":[],"published":{"date-parts":[[2008,3,5]]}}}