{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:49:51Z","timestamp":1763808591167},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,2]]},"abstract":"<jats:p>We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show \u03a9(n log n) time lower bounds for separability by means of strips, wedges, wedges with apices on a given line, fixed-slopes double wedges, and triangles, which match the complexity of the existing algorithms, and therefore prove their optimality.<\/jats:p>","DOI":"10.1142\/s0218195906001902","type":"journal-article","created":{"date-parts":[[2006,2,24]],"date-time":"2006-02-24T11:22:29Z","timestamp":1140780149000},"page":"1-26","source":"Crossref","is-referenced-by-count":13,"title":["SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS"],"prefix":"10.1142","volume":"16","author":[{"given":"ESTHER M.","family":"ARKIN","sequence":"first","affiliation":[{"name":"Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FERRAN","family":"HURTADO","sequence":"additional","affiliation":[{"name":"Dpt. Matem\u00e0tica Aplicada II, Univ. Polit\u00e8cnica de Catalunya, 08034 Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOSEPH S. B.","family":"MITCHELL","sequence":"additional","affiliation":[{"name":"Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CARLOS","family":"SEARA","sequence":"additional","affiliation":[{"name":"Dpt. Matem\u00e0tica Aplicada II, Univ. Polit\u00e8cnica de Catalunya, 08034 Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STEVEN S.","family":"SKIENA","sequence":"additional","affiliation":[{"name":"Computer Science, Stony Brook University, Stony Brook, NY 11794, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90049-7"},{"key":"rf4","volume-title":"Computational Morphology","author":"Bhathacharya B. K.","year":"1988"},{"key":"rf5","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1142\/S0218195900000036","volume":"10","author":"Boissonnat J.-D.","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90049-1"},{"key":"rf9","first-page":"554","volume":"8","author":"Fisk S.","journal-title":"IEEE Trans. Patt. Anal. Mach. Intell."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015626820950"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90057-U"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00230-4"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.11.014"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840442"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187688"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90141-4"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906001902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,12]],"date-time":"2020-04-12T22:09:18Z","timestamp":1586729358000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906001902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,2]]},"references-count":13,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,2]]}},"alternative-id":["10.1142\/S0218195906001902"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906001902","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,2]]}}}