{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:34:34Z","timestamp":1772516074727,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s00454-007-9046-6","type":"journal-article","created":{"date-parts":[[2007,12,20]],"date-time":"2007-12-20T09:30:31Z","timestamp":1198143031000},"page":"656-677","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Algorithms for Maximum Regression Depth"],"prefix":"10.1007","volume":"39","author":[{"given":"Marc","family":"van Kreveld","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Rousseeuw","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bettina","family":"Speckmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,12,21]]},"reference":[{"key":"9046_CR1","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1006\/jmva.1999.1870","volume":"73","author":"S.V. Aelst","year":"2000","unstructured":"Aelst, S.V., Rousseeuw, P.J.: Robustness of deepest regression. J. Multivar. Anal. 73, 82\u2013106 (2000)","journal-title":"J. Multivar. Anal."},{"issue":"1","key":"9046_CR2","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jmva.2001.1997","volume":"81","author":"S.V. Aelst","year":"2002","unstructured":"Aelst, S.V., Rousseeuw, P.J., Hubert, M., Struyf, A.: The deepest regression method. J. Multivar. Anal. 81(1), 138\u2013166 (2002)","journal-title":"J. Multivar. Anal."},{"key":"9046_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/PL00009502","volume":"23","author":"N. Amenta","year":"2000","unstructured":"Amenta, N., Bern, M., Eppstein, D., Teng, S.-H.: Regression depth and center points. Discrete Comput. Geom. 23, 305\u2013323 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"9046_CR4","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proc. 43rd Symposium on Foundations of Computer Science (FOCS), pp.\u00a0617\u2013626 (2002)","DOI":"10.1109\/SFCS.2002.1181985"},{"issue":"1","key":"9046_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0925-7721(97)00025-4","volume":"10","author":"H. Br\u00f6nnimann","year":"1998","unstructured":"Br\u00f6nnimann, H., Chazelle, B.: Optimal slope selection via cuttings. Comput. Geom. Theory Appl. 10(1), 23\u201329 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"9046_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/363647.363652","volume":"48","author":"T.M. Chan","year":"2001","unstructured":"Chan, T.M.: Dynamic planar convex hull operations in near-logarithmic amortized time. J. ACM 48(1), 1\u201312 (2001)","journal-title":"J. ACM"},{"key":"9046_CR7","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum turkey depth. In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0430\u2013436 (2004)"},{"issue":"2","key":"9046_CR8","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9046_CR9","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02187685","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Preparata, F.P.: Halfspace range search: An algorithmic application of k-sets. Discrete Comput. Geom. 1, 83\u201393 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9046_CR10","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R. Cole","year":"1989","unstructured":"Cole, R., Salowe, J., Steiger, W., Szemer\u00e9di, E.: An optimal-time algorithm for slope selection. SIAM J. Comput. 18(4), 792\u2013810 (1989)","journal-title":"SIAM J. Comput."},{"key":"9046_CR11","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T.K. Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds on planar k-sets and related problems. Discrete Comput. Geom. 19, 373\u2013382 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"9046_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0218195992000020","volume":"2","author":"M.B. Dillencourt","year":"1992","unstructured":"Dillencourt, M.B., Mount, D.M., Netanyahu, N.S.: A randomized algorithm for slope selection. Int. J. Comput. Geom. Appl. 2, 1\u201327 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9046_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, New York (1987)"},{"key":"9046_CR14","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput 15, 341\u2013363 (1986)","journal-title":"SIAM J. Comput"},{"issue":"2","key":"9046_CR15","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H. Edelsbrunner","year":"1993","unstructured":"Edelsbrunner, H., Seidel, R., Sharir, M.: On the zone theorem for hyperplane arrangements. SIAM J. Comput. 22(2), 418\u2013429 (1993)","journal-title":"SIAM J. Comput."},{"key":"9046_CR16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/jagm.1996.0040","volume":"21","author":"D. Eu","year":"1996","unstructured":"Eu, D., Gu\u00e9vremont, E., Toussaint, G.T.: On envelopes of arrangements of lines. J. Algorithms 21, 111\u2013148 (1996)","journal-title":"J. Algorithms"},{"key":"9046_CR17","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0925-7721(95)00020-8","volume":"6","author":"L.J. Guibas","year":"1996","unstructured":"Guibas, L.J., Overmars, M.H., Robert, J.-M.: The exact fitting problem for points. Comput. Geom. Theory Appl. 6, 215\u2013230 (1996)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9046_CR18","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1006\/jmva.1998.1751","volume":"66","author":"M. Hubert","year":"1998","unstructured":"Hubert, M., Rousseeuw, P.J.: The catline for deep regression. J. Multivar. Anal. 66, 270\u2013296 (1998)","journal-title":"J. Multivar. Anal."},{"key":"9046_CR19","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(93)90234-Z","volume":"47","author":"M.J. Katz","year":"1993","unstructured":"Katz, M.J., Sharir, M.: Optimal slope selection via expanders. Inf. Process. Lett. 47, 115\u2013122 (1993)","journal-title":"Inf. Process. Lett."},{"key":"9046_CR20","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(91)90106-R","volume":"39","author":"M. Keil","year":"1991","unstructured":"Keil, M.: A simple algorithm for determining the envelope of a set of lines. Inf. Process. Lett. 39, 121\u2013124 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9046_CR21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s00454-003-0011-x","volume":"30","author":"S. Langerman","year":"2003","unstructured":"Langerman, S., Steiger, W.: The complexity of hyperplane depth in the plane. Discrete Comput. Geom. 30(2), 299\u2013309 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"9046_CR22","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0020-0190(91)90177-J","volume":"39","author":"J. Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Randomized optimal algorithm for slope selection. Inf. Process. Lett. 39, 183\u2013187 (1991)","journal-title":"Inf. Process. Lett."},{"key":"9046_CR23","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0012-365X(85)90193-1","volume":"56","author":"G.W. Peck","year":"1985","unstructured":"Peck, G.W.: On k-sets in the plane. Discrete Math. 56, 73\u201374 (1985)","journal-title":"Discrete Math."},{"key":"9046_CR24","first-page":"419","volume":"94","author":"P.J. Rousseeuw","year":"1999","unstructured":"Rousseeuw, P.J., Aelst, S.V., Hubert, M.: Regression depth: Rejoinder. J. Am. Stat. Assoc. 94, 419\u2013433 (1999)","journal-title":"J. Am. Stat. Assoc."},{"key":"9046_CR25","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/PL00009452","volume":"22","author":"P.J. Rousseeuw","year":"1999","unstructured":"Rousseeuw, P.J., Hubert, M.: Depth in an arrangement of hyperplanes. Discrete Comput. Geom. 22, 167\u2013176 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9046_CR26","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1080\/01621459.1999.10474129","volume":"94","author":"P.J. Rousseeuw","year":"1999","unstructured":"Rousseeuw, P.J., Hubert, M.: Regression depth. J. Am. Stat. Assoc. 94, 388\u2013402 (1999)","journal-title":"J. Am. Stat. Assoc."},{"key":"9046_CR27","first-page":"827","volume":"8","author":"P.J. Rousseeuw","year":"1998","unstructured":"Rousseeuw, P.J., Ruts, I.: Constructing the bivariate Tukey median. Stat. Sin. 8, 827\u2013839 (1998)","journal-title":"Stat. Sin."},{"key":"9046_CR28","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/A:1008945009397","volume":"8","author":"P.J. Rousseeuw","year":"1998","unstructured":"Rousseeuw, P.J., Struyf, A.: Computing location depth and regression depth in higher dimensions. Stat. Comput. 8, 193\u2013203 (1998)","journal-title":"Stat. Comput."},{"key":"9046_CR29","first-page":"1279","volume-title":"The Handbook of Discrete and Computational Geometry","author":"P.J. Rousseeuw","year":"2004","unstructured":"Rousseeuw, P.J., Struyf, A.: Computation of robust statistics: depth, median, and related measures. In: Goodman, J.E., O\u2019Rourke, J. (eds.) The Handbook of Discrete and Computational Geometry, 2nd edn., pp. 1279\u20131292. Chapman & Hall\/CRC, Boca Raton (2004)","edition":"2"},{"key":"9046_CR30","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":"9046_CR31","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/BF01303520","volume":"13","author":"M. Sharir","year":"1993","unstructured":"Sharir, M.: k-sets and random hulls. Combinatorica 13, 483\u2013495 (1993)","journal-title":"Combinatorica"},{"key":"9046_CR32","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1006\/jmva.1998.1804","volume":"69","author":"A. Struyf","year":"1999","unstructured":"Struyf, A., Rousseeuw, P.J.: Halfspace depth and regression depth characterize the empirical distribution. J. Multivar. Anal. 69, 135\u2013153 (1999)","journal-title":"J. Multivar. Anal."},{"key":"9046_CR33","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/S0167-9473(99)00112-7","volume":"34","author":"A. Struyf","year":"2000","unstructured":"Struyf, A., Rousseeuw, P.J.: High-dimensional computation of the deepest location. Comput. Stat. Data Anal. 34, 415\u2013426 (2000)","journal-title":"Comput. Stat. Data Anal."},{"key":"9046_CR34","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s004540010022","volume":"26","author":"G. T\u00f3th","year":"2001","unstructured":"T\u00f3th, G.: Point sets with many k-sets. Discrete Comput. Geom. 26, 187\u2013194 (2001)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-007-9046-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T09:19:36Z","timestamp":1549444776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-007-9046-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,21]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["9046"],"URL":"https:\/\/doi.org\/10.1007\/s00454-007-9046-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,21]]}}}