{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:06:23Z","timestamp":1777539983771,"version":"3.51.4"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:p> We study the complexity of the following cell connection problems in segment arrangements. Given a set of straight-line segments in the plane and two points [Formula: see text] and [Formula: see text] in different cells of the induced arrangement: <\/jats:p><jats:p> [(i)] compute the minimum number of segments one needs to remove so that there is a path connecting [Formula: see text] to [Formula: see text] that does not intersect any of the remaining segments; [(ii)] compute the minimum number of segments one needs to remove so that the arrangement induced by the remaining segments has a single cell. <\/jats:p><jats:p> We show that problems (i) and (ii) are NP-hard and discuss some special, tractable cases. Most notably, we provide a near-linear-time algorithm for a variant of problem (i) where the path connecting [Formula: see text] to [Formula: see text] must stay inside a given polygon [Formula: see text] with a constant number of holes, the segments are contained in [Formula: see text], and the endpoints of the segments are on the boundary of [Formula: see text]. The approach for this latter result uses homotopy of paths to group the segments into clusters with the property that either all segments in a cluster or none participate in an optimal solution. <\/jats:p>","DOI":"10.1142\/s0218195917500017","type":"journal-article","created":{"date-parts":[[2018,1,30]],"date-time":"2018-01-30T06:09:42Z","timestamp":1517292582000},"page":"159-176","source":"Crossref","is-referenced-by-count":4,"title":["Minimum Cell Connection in Line Segment Arrangements"],"prefix":"10.1142","volume":"27","author":[{"given":"Helmut","family":"Alt","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Takustra\u00dfe 9, D-14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[{"name":"Department of Mathematics, IMFM and FMF, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panos","family":"Giannopoulos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, School of Science and Technology, Middlesex University, The Burroughs, Hendon, London NW4 4BT, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Knauer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Bayreuth, Universit\u00e4tsstra\u00dfe 30, D-95447 Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,1,29]]},"reference":[{"key":"S0218195917500017BIB003","first-page":"299","volume":"31","author":"Broersma H.","year":"2005","journal-title":"Australasian J. Combin."},{"key":"S0218195917500017BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2949-y"},{"key":"S0218195917500017BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"S0218195917500017BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"S0218195917500017BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570705"},{"key":"S0218195917500017BIB008","first-page":"109","volume":"63","author":"de Fraysseix H.","year":"1991","journal-title":"Intuitive Geom."},{"key":"S0218195917500017BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.02.012"},{"key":"S0218195917500017BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187744"},{"key":"S0218195917500017BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90069-E"},{"key":"S0218195917500017BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9044-x"},{"key":"S0218195917500017BIB014","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"S0218195917500017BIB015","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"S0218195917500017BIB016","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"S0218195917500017BIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195914600048"},{"key":"S0218195917500017BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-006-9856-0"},{"key":"S0218195917500017BIB021","doi-asserted-by":"publisher","DOI":"10.1137\/0219040"},{"key":"S0218195917500017BIB024","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","year":"2001"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195917500017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:19:56Z","timestamp":1565119196000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195917500017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":17,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2018,1,29]]},"published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.1142\/S0218195917500017"],"URL":"https:\/\/doi.org\/10.1142\/s0218195917500017","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9]]}}}