{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:49:17Z","timestamp":1763808557621},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2005,8]]},"abstract":"<jats:p>We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords.<\/jats:p>","DOI":"10.1142\/s0218195905001762","type":"journal-article","created":{"date-parts":[[2005,8,22]],"date-time":"2005-08-22T11:56:45Z","timestamp":1124711805000},"page":"403-419","source":"Crossref","is-referenced-by-count":14,"title":["SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS"],"prefix":"10.1142","volume":"15","author":[{"given":"ERIK D.","family":"DEMAINE","sequence":"first","affiliation":[{"name":"MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., Cambridge, MA 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JEFF","family":"ERICKSON","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue, Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FERRAN","family":"HURTADO","sequence":"additional","affiliation":[{"name":"Departement de Matem\u00e0tica Aplicada II, Universitat Polit\u00e8cnica de Catalunya, Pau Gargallo 5, 08028 Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOHN","family":"IACONO","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, Polytechnic University, 5 MetroTech Center, Brooklyn, NY 11201, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STEFAN","family":"LANGERMAN","sequence":"additional","affiliation":[{"name":"D\u00e9partement d'Informatique, Universit\u00e9 Libre de Bruxelles, ULB CP212, 1050 Bruxelles, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HENK","family":"MEIJER","sequence":"additional","affiliation":[{"name":"School of Computing, Queen's University, Kingston, Ontario, K7L 3N6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARK","family":"OVERMARS","sequence":"additional","affiliation":[{"name":"Institute of Information and Computing Sciences, Utrecht University, P.O.Box 80.089, 3508 TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SUE","family":"WHITESIDES","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, 3480 University St. room 318, Montreal, Quebec H3A 2A7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553882"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189321"},{"key":"rf3","volume-title":"Computational Morphology","author":"Bhathacharya B. K.","year":"1988"},{"key":"rf4","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1142\/S0218195900000036","volume":"10","author":"Boissonnat J.-D.","journal-title":"Int. J. Comput. Geom. Appli."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90049-1"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90041-X"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00230-4"},{"key":"rf11","first-page":"389","author":"Laroche P.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009199"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187751"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90045-7"},{"key":"rf18","unstructured":"G.\u00a0Toussaint and T.\u00a0Asano, Discrete Algorithms and Complexity, Perspectives in Computing (Academic Press, 1987)\u00a0pp. 65\u201379."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1137\/0220041"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195905001762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T04:41:27Z","timestamp":1586407287000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195905001762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":15,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1142\/S0218195905001762"],"URL":"https:\/\/doi.org\/10.1142\/s0218195905001762","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}