{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T09:56:43Z","timestamp":1768471003519,"version":"3.49.0"},"reference-count":16,"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> Helly\u2019s theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If [Formula: see text] is a set of [Formula: see text] points in [Formula: see text], we say that [Formula: see text] is [Formula: see text]-clusterable if it can be partitioned into [Formula: see text] clusters (subsets) such that each cluster can be contained in a translated copy of a geometric object [Formula: see text]. In this paper, as an application of Helly\u2019s theorem, by taking a constant size sample from [Formula: see text], we present a testing algorithm for [Formula: see text]-clustering, i.e., to distinguish between the following two cases: when [Formula: see text] is [Formula: see text]-clusterable, and when it is [Formula: see text]-far from being [Formula: see text]-clusterable. A set [Formula: see text] is [Formula: see text]-far [Formula: see text] from being [Formula: see text]-clusterable if at least [Formula: see text] points need to be removed from [Formula: see text] in order to make it [Formula: see text]-clusterable. We solve this problem when [Formula: see text], and [Formula: see text] is a symmetric convex object. For [Formula: see text], we solve a weaker version of this problem. Finally, as an application of our testing result, in the case of clustering with outliers, we show that with high probability one can find the approximate clusters by querying only a constant size sample. <\/jats:p>","DOI":"10.1142\/s0218195918500115","type":"journal-article","created":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T23:32:53Z","timestamp":1555025573000},"page":"365-379","source":"Crossref","is-referenced-by-count":1,"title":["Helly-Type Theorems in Property Testing"],"prefix":"10.1142","volume":"28","author":[{"given":"Sourav","family":"Chakraborty","sequence":"first","affiliation":[{"name":"Chennai Mathematical Institute, H1, SIPCOT IT Park, Siruseri, Kelambakkam 603103, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8824-6202","authenticated-orcid":false,"given":"Rameshwar","family":"Pratap","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology, 26\/C, Hosur Rd, Electronics City Phase 1, Electronic City, Bengaluru, Karnataka 560100, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasanka","family":"Roy","sequence":"additional","affiliation":[{"name":"ACM Unit, Indian Statistical Institute, 203, B T Road, Kolkata 700108, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Department of Computer Science, Hill Centre, Room 426, Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2019,4,11]]},"reference":[{"key":"S0218195918500115BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102410973"},{"key":"S0218195918500115BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80029-9"},{"key":"S0218195918500115BIB003","volume-title":"Cluster Analysis for Applications","author":"Anderberg M. R.","year":"1973"},{"key":"S0218195918500115BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579232"},{"issue":"2","key":"S0218195918500115BIB008","first-page":"217","volume":"19","author":"Eckhoff J.","year":"1985","journal-title":"Geom. Dediata"},{"key":"S0218195918500115BIB010","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1990"},{"key":"S0218195918500115BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"S0218195918500115BIB013","first-page":"175","volume":"32","author":"Helly E.","year":"1923","journal-title":"Jahresber. Deutsch. Math. Verein."},{"key":"S0218195918500115BIB014","volume-title":"Algorithms for Clustering","author":"Jain A. K.","year":"1988"},{"key":"S0218195918500115BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761162"},{"key":"S0218195918500115BIB016","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-96-03806-3"},{"key":"S0218195918500115BIB017","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316801"},{"key":"S0218195918500115BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.034"},{"key":"S0218195918500115BIB019","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.498"},{"key":"S0218195918500115BIB020","first-page":"284","volume":"75","author":"Katchalski M.","year":"1979","journal-title":"Proc. AMS"},{"key":"S0218195918500115BIB021","doi-asserted-by":"publisher","DOI":"10.1561\/2200000004"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195918500115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T10:39:32Z","timestamp":1565174372000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195918500115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12]]},"references-count":16,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2019,4,11]]},"published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1142\/S0218195918500115"],"URL":"https:\/\/doi.org\/10.1142\/s0218195918500115","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12]]}}}