{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:29:20Z","timestamp":1750246160966,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00224-021-10067-4","type":"journal-article","created":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T07:02:35Z","timestamp":1641625355000},"page":"417-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing Colourful Simplicial Depth and Median in \u211d2"],"prefix":"10.1007","volume":"66","author":[{"given":"Greg","family":"Aloupis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0156-7415","authenticated-orcid":false,"given":"Tamon","family":"Stephen","sequence":"additional","affiliation":[]},{"given":"Olga","family":"Zasenko","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,8]]},"reference":[{"issue":"6","key":"10067_CR1","doi-asserted-by":"publisher","first-page":"1894","DOI":"10.1093\/imrn\/rnx184","volume":"2019","author":"KA Adiprasito","year":"2017","unstructured":"Adiprasito, K.A., Brinkmann, P., Padrol, A., Pat\u00e1k, P., Pat\u00e1kov\u00e1, Z., Sanyal, R.: Colorful Simplicial Depth, Minkowski Sums, and Generalized Gale Transforms. Int. Math. Res. Not. 2019(6), 1894\u20131919 (2017)","journal-title":"Int. Math. Res. Not."},{"key":"10067_CR2","unstructured":"Afshani, P., Sheehy, D.R., Stein, Y.: Approximating the simplicial depth in high dimensions. The European Workshop on Computational Geometry (2016)"},{"key":"10067_CR3","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0304-0208(08)73484-4","volume":"60","author":"M Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. North-Holland Math. Stud. 60, 9\u201312 (1982)","journal-title":"North-Holland Math. Stud."},{"key":"10067_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1090\/dimacs\/072\/10","volume":"72","author":"G Aloupis","year":"2006","unstructured":"Aloupis, G.: Geometric measures of data depth, Data depth: robust multivariate analysis, computational geometry and applications. DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence, RI 72, 147\u2013158 (2006)","journal-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence, RI"},{"issue":"2","key":"10067_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0167-9473(02)00032-4","volume":"40","author":"G Aloupis","year":"2002","unstructured":"Aloupis, G., Cort\u00e9s, C., G\u00f3mez, F., Soss, M., Toussaint, G.: Lower bounds for computing statistical depth. Comput. Stat. Data Anal. 40 (2), 223\u2013229 (2002)","journal-title":"Comput. Stat. Data Anal."},{"issue":"1","key":"10067_CR6","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0925-7721(02)00173-6","volume":"26","author":"G Aloupis","year":"2003","unstructured":"Aloupis, G., Langerman, S., Soss, M., Toussaint, G.: Algorithms for bivariate medians and a Fermat-Torricelli problem for lines. Comput. Geom. 26(1), 69\u201379 (2003)","journal-title":"Comput. Geom."},{"issue":"2-3","key":"10067_CR7","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(82)90115-7","volume":"40","author":"I B\u00e1r\u00e1ny","year":"1982","unstructured":"B\u00e1r\u00e1ny, I.: A generalization of Carath\u00e9odory\u2019s theorem. Discrete Math. 40(2-3), 141\u2013152 (1982)","journal-title":"Discrete Math."},{"issue":"3","key":"10067_CR8","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1287\/moor.22.3.550","volume":"22","author":"I B\u00e1r\u00e1ny","year":"1997","unstructured":"B\u00e1r\u00e1ny, I., Onn, S.: Colourful linear programming and its relatives. Math. Oper. Res. 22(3), 550\u2013567 (1997)","journal-title":"Math. Oper. Res."},{"key":"10067_CR9","unstructured":"Cheng, A.Y., Ouyang, M.: On algorithms for simplicial depth. In: Proceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Canada, August 13-15, 2001, pp 53\u201356 (2001)"},{"issue":"4","key":"10067_CR10","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00454-006-1233-3","volume":"35","author":"A Deza","year":"2006","unstructured":"Deza, A., Huang, S., Stephen, T., Terlaky, T.: Colourful simplicial depth. Discrete Comput. Geom. 35(4), 597\u2013615 (2006)","journal-title":"Discrete Comput. Geom."},{"issue":"11","key":"10067_CR11","doi-asserted-by":"publisher","first-page":"2166","DOI":"10.1016\/j.dam.2008.01.016","volume":"156","author":"A Deza","year":"2008","unstructured":"Deza, A., Huang, S., Stephen, T., Terlaky, T.: The colourful feasibility problem. Discrete Appl. Math. 156(11), 2166\u20132177 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10067_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38(1), 165\u2013194 (1989). 18Th Annual ACM Symposium on Theory of Computing (Berkeley, CA, 1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"10067_CR13","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., M\u00fccke, E.P.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. In: Proceedings of the Fourth Annual Symposium on Computational Geometry (Urbana, IL, 1988), pp 118\u2013133. ACM, New York (1988)","DOI":"10.1145\/73393.73406"},{"issue":"5","key":"10067_CR14","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1142\/S0218195911003779","volume":"21","author":"K Elbassioni","year":"2011","unstructured":"Elbassioni, K., Elmasry, A., Makino, K.: Finding simplices containing the origin in two and three dimensions. Int. J. Comput. Geom. Appl. 21(5), 495\u2013506 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"10067_CR15","unstructured":"Elmasry, A., Elbassioni, K.M.: Output-sensitive algorithms for enumerating and counting simplices containing a given point in th plane. In: 17th Canadian Conference on Computational Geometry (CCCG\u201905) (Windsor, Canada), no. 17, University of Windsor, pp 248\u2013251 (2005)"},{"key":"10067_CR16","first-page":"37","volume-title":"Data depth and maximum feasible subsystems, Graph theory and combinatorial optimization, GERAD 25th Anniv. Ser., vol. 8","author":"K Fukuda","year":"2005","unstructured":"Fukuda, K., Rosta, V.: Data depth and maximum feasible subsystems, Graph theory and combinatorial optimization, GERAD 25th Anniv. Ser., vol. 8, pp 37\u201367. Springer, New York (2005)"},{"issue":"4","key":"10067_CR17","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1002\/jgt.22041","volume":"84","author":"E Gethner","year":"2016","unstructured":"Gethner, E., Hogben, L., Lidick\u00fd, B., Pfender, F., Ruiz, A., Young, M.: On crossing numbers of complete tripartite and balanced complete multipartite graphs. J. Graph Theory 84(4), 552\u2013565 (2016)","journal-title":"J. Graph Theory"},{"issue":"1-3","key":"10067_CR18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(92)90658-3","volume":"108","author":"J Gil","year":"1992","unstructured":"Gil, J., Steiger, W., Wigderson, A.: Geometric medians. Discrete Math. 108(1-3), 37\u201351 (1992)","journal-title":"Discrete Math."},{"issue":"6","key":"10067_CR19","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0020-0190(90)90217-L","volume":"33","author":"S Khuller","year":"1990","unstructured":"Khuller, S., Mitchell, J.S.B.: On a triangle counting problem. Inform. Process. Lett. 33(6), 319\u2013321 (1990)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"10067_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0020-0190(85)90015-8","volume":"21","author":"DT Lee","year":"1985","unstructured":"Lee, D.T., Ching, Y.T.: The power of geometric duality revisited. Inform. Process. Lett. 21(3), 117\u2013122 (1985)","journal-title":"Inform. Process. Lett."},{"key":"10067_CR21","unstructured":"Leighton, F.T.: Complexity issues in VLSI, Foundations of Computing Series, MIT Press (1983)"},{"issue":"1","key":"10067_CR22","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1214\/aos\/1176347507","volume":"18","author":"RY Liu","year":"1990","unstructured":"Liu, R.Y.: On a notion of data depth based on random simplices. Ann. Statist. 18(1), 405\u2013414 (1990)","journal-title":"Ann. Statist."},{"issue":"1","key":"10067_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00454-014-9584-7","volume":"52","author":"J Matou\u0161ek","year":"2014","unstructured":"Matou\u0161ek, J., Wagner, U.: On Gromov\u2019s method of selecting heavily covered points. Discrete Comput. Geom. 52(1), 1\u201333 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"10067_CR24","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.dam.2016.10.006","volume":"240","author":"F Meunier","year":"2018","unstructured":"Meunier, F., Sarrabezolles, P.: Colorful linear programming, Nash equilibrium, and pivots. Discret. Appl. Math. 240, 78\u201391 (2018)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"10067_CR25","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1007\/s00454-018-9979-y","volume":"60","author":"W Mulzer","year":"2018","unstructured":"Mulzer, W., Stein, Y.: Computational aspects of the colorful Carath\u00e9odory theorem. Discret. Comput. Geom. 60(3), 720\u2013755 (2018)","journal-title":"Discret. Comput. Geom."},{"key":"10067_CR26","unstructured":"Pilz, A., Welzl, E., Wettstein, M.: From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices. In: 33rd International Symposium on Computational Geometry (SoCG 2017), vol. 77, pp 54:1\u201354:16 (2017)"},{"issue":"17","key":"10067_CR27","doi-asserted-by":"publisher","first-page":"3276","DOI":"10.1016\/j.dam.2008.06.019","volume":"156","author":"E Rafalin","year":"2008","unstructured":"Rafalin, E., Souvaine, D.L.: Topological sweep of the complete graph. Discrete Appl. Math. 156(17), 3276\u20133290 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"10067_CR28","first-page":"516","volume":"45","author":"PJ Rousseeuw","year":"1996","unstructured":"Rousseeuw, P.J., Ruts, I.: Bivariate location depth. Appl. Stat. J. Royal Stat. Soc. Series C 45(4), 516\u2013526 (1996)","journal-title":"Appl. Stat. J. Royal Stat. Soc. Series C"},{"key":"10067_CR29","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jcta.2014.11.002","volume":"130","author":"P Sarrabezolles","year":"2015","unstructured":"Sarrabezolles, P.: The colourful simplicial depth conjecture. J. Combin. Theory Ser. A 130, 119\u2013128 (2015)","journal-title":"J. Combin. Theory Ser. A"},{"key":"10067_CR30","unstructured":"Zasenko, O.: Colourful simplicial depth in the plane, 2016, Java code, available at http:\/\/github.com\/olgazasenko\/ColourfulSimplicialDepthInThePlane Accessed February 2nd (2017)"},{"key":"10067_CR31","doi-asserted-by":"crossref","unstructured":"Zasenko, O., Stephen, T.: Algorithms for colourful simplicial depth and medians in the plane. In: Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings, Lecture Notes in Comput. Sci, vol. 10043, pp 378\u2013392. Springer (2016)","DOI":"10.1007\/978-3-319-48749-6_28"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10067-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10067-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10067-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T05:03:07Z","timestamp":1651554187000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10067-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,8]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10067"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10067-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,1,8]]},"assertion":[{"value":"5 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}