{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:40Z","timestamp":1740120220818,"version":"3.37.3"},"reference-count":29,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p> Given a set [Formula: see text] of points and a point [Formula: see text] in the plane, we define a function [Formula: see text] that provides a combinatorial characterization of the multiset of values [Formula: see text], where for each [Formula: see text], [Formula: see text] is the open half-plane determined by [Formula: see text] and [Formula: see text]. We introduce two new natural measures of depth, perihedral depth and eutomic depth, and we show how to express these and the well-known simplicial and Tukey depths concisely in terms of [Formula: see text]. The perihedral and eutomic depths of [Formula: see text] with respect to [Formula: see text] correspond respectively to the number of subsets of [Formula: see text] whose convex hull contains [Formula: see text], and the number of combinatorially distinct bisections of [Formula: see text] determined by a line through [Formula: see text]. We present algorithms to compute the depth of an arbitrary query point in [Formula: see text] time and medians (deepest points) with respect to these depth measures in [Formula: see text] and [Formula: see text] time respectively. For comparison, these results match or slightly improve on the corresponding best-known running times for simplicial depth, whose definition involves similar combinatorial complexity. <\/jats:p>","DOI":"10.1142\/s0218195918500127","type":"journal-article","created":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T23:32:53Z","timestamp":1555025573000},"page":"381-398","source":"Crossref","is-referenced-by-count":1,"title":["On Combinatorial Depth Measures"],"prefix":"10.1142","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6589-3538","authenticated-orcid":false,"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[{"name":"University of Manitoba, Winnipeg, Canada"}]},{"given":"Robert","family":"Fraser","sequence":"additional","affiliation":[{"name":"University of Manitoba, Winnipeg, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2282-410X","authenticated-orcid":false,"given":"Alexandre","family":"Leblanc","sequence":"additional","affiliation":[{"name":"University of Manitoba, Winnipeg, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6973-3227","authenticated-orcid":false,"given":"Jason","family":"Morrison","sequence":"additional","affiliation":[{"name":"University of Manitoba, Winnipeg, Canada"}]},{"given":"Matthew","family":"Skala","sequence":"additional","affiliation":[{"name":"North Coast Synthesis Ltd., Toronto, Canada"}]}],"member":"219","published-online":{"date-parts":[[2019,4,11]]},"reference":[{"key":"S0218195918500127BIB001","first-page":"147","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume":"72","author":"Aloupis G.","year":"2006"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB002","DOI":"10.1016\/S0167-9473(02)00032-4"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB003","DOI":"10.1016\/S0925-7721(02)00173-6"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB004","DOI":"10.1007\/BF02187906"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB005","DOI":"10.2307\/2344839"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB006","DOI":"10.1016\/S0925-7721(02)00102-5"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB007","DOI":"10.1007\/s11222-008-9054-2"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB009","DOI":"10.1090\/S0002-9939-96-03657-X"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB010","DOI":"10.1111\/1467-9868.00114"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB012","DOI":"10.1016\/j.comgeo.2013.06.005"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB013","DOI":"10.1016\/j.comgeo.2012.03.001"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB014","DOI":"10.1016\/S0169-7439(99)00047-7"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB015","DOI":"10.1007\/PL00009354"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB018","DOI":"10.1016\/0022-0000(89)90038-X"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB019","DOI":"10.1142\/S0218195911003779"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB020","DOI":"10.1214\/lnms\/1215454155"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB021","DOI":"10.1007\/BF02595872"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB023","DOI":"10.1137\/0212002"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB024","DOI":"10.1214\/aos\/1069362382"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB026","DOI":"10.1214\/aos\/1176347507"},{"issue":"421","key":"S0218195918500127BIB027","first-page":"252","volume":"88","author":"Liu R. Y.","year":"1993","journal-title":"J. ASA"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB028","DOI":"10.1080\/10485252.2011.584621"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB029","DOI":"10.1090\/dimacs\/072\/04"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB031","DOI":"10.1016\/0167-7152(83)90054-8"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB032","DOI":"10.1007\/978-94-009-5438-0_20"},{"issue":"4","key":"S0218195918500127BIB033","first-page":"516","volume":"45","author":"Rousseeuw P. J.","year":"1996","journal-title":"J. Roy. Stat. Soc. Ser. C (Appl. Stat.)"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB035","DOI":"10.2307\/1403809"},{"issue":"3","key":"S0218195918500127BIB036","first-page":"227","volume":"27","author":"Titterington D. M.","year":"1978","journal-title":"J. Roy. Stat. Soc. Ser. C (Appl. Stat.)"},{"doi-asserted-by":"publisher","key":"S0218195918500127BIB039","DOI":"10.1214\/aos\/1016218226"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195918500127","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T10:39:33Z","timestamp":1565174373000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195918500127"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12]]},"references-count":29,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2019,4,11]]},"published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1142\/S0218195918500127"],"URL":"https:\/\/doi.org\/10.1142\/s0218195918500127","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2018,12]]}}}