{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:29:19Z","timestamp":1753885759745,"version":"3.41.2"},"reference-count":31,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/100000001","name":"national science foundation","doi-asserted-by":"publisher","award":["CCF-1614562"],"award-info":[{"award-number":["CCF-1614562"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p> In this paper, we prove that the uncertain segment cover problem is NP-hard. The uncertain segment cover problem, which appears in solving the question of visibility of a segment in the plane from a given point in the presence of uncertain obstacles, asks if a given interval can be covered by a collection of uncertain sub-intervals having two possible positions. This is done by showing that this problem is equivalent to a special version of the SAT problem that we will call contiguous SAT. In a contiguous SAT problem a CNF formula with a given ordering on its clauses is given such that any literal appears contiguously. We prove that contiguous SAT problem is NP-hard and as a consequence it follows that the uncertain segment cover problem is NP-hard. The approximation solution of this problem and its hardness are also studied. <\/jats:p>","DOI":"10.1142\/s179383092250063x","type":"journal-article","created":{"date-parts":[[2022,4,23]],"date-time":"2022-04-23T04:51:05Z","timestamp":1650689465000},"source":"Crossref","is-referenced-by-count":0,"title":["Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles"],"prefix":"10.1142","volume":"15","author":[{"given":"Sharareh","family":"Alipour","sequence":"first","affiliation":[{"name":"School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Iran"}]},{"given":"Salman","family":"Parsa","sequence":"additional","affiliation":[{"name":"Computer Science Department, Saint Louis University, USA"}]}],"member":"219","published-online":{"date-parts":[[2022,4,22]]},"reference":[{"key":"S179383092250063XBIB001","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2019.01.035","volume":"779","author":"Abam M. A.","year":"2019","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"S179383092250063XBIB002","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.tcs.2005.11.030","volume":"354","author":"Asano T.","year":"2006","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"S179383092250063XBIB003","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1006\/jagm.2001.1202","volume":"42","author":"Asano T.","year":"2002","journal-title":"J. Algorithms"},{"issue":"12","key":"S179383092250063XBIB004","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1109\/TC.1981.1675729","volume":"30","author":"Avis D.","year":"1981","journal-title":"IEEE Trans. Comput."},{"first-page":"27","volume-title":"Proc. 20th ACM Symp. Computational Geometry","author":"Ben-Moshe B.","key":"S179383092250063XBIB005"},{"issue":"3","key":"S179383092250063XBIB006","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01758843","volume":"8","author":"Briggs A. J.","year":"1992","journal-title":"Algorithmica"},{"first-page":"94","volume-title":"Proc. Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015","author":"Buchin K.","key":"S179383092250063XBIB007"},{"issue":"3","key":"S179383092250063XBIB008","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/PL00009467","volume":"22","author":"Carlsson S.","year":"1999","journal-title":"Discrete Comput. Geom."},{"first-page":"434","volume-title":"Algorithms and Computation \u2014 21st Int. Symp., ISAAC 2010","author":"Chambers E. W.","key":"S179383092250063XBIB009"},{"issue":"3","key":"S179383092250063XBIB010","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1007\/s00453-016-0191-2","volume":"78","author":"Chambers E. W.","year":"2017","journal-title":"Algorithmica"},{"key":"S179383092250063XBIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187747"},{"key":"S179383092250063XBIB012","doi-asserted-by":"publisher","DOI":"10.1137\/060665257"},{"issue":"4","key":"S179383092250063XBIB013","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"Dahlhaus E.","year":"1994","journal-title":"SIAM J. Comput."},{"issue":"3","key":"S179383092250063XBIB014","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01840394","volume":"5","author":"Donald B. R.","year":"1990","journal-title":"Algorithmica"},{"key":"S179383092250063XBIB015","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543340"},{"key":"S179383092250063XBIB016","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"first-page":"77","volume-title":"Proc. 26th ACM Symp. Computational Geometry","author":"Gudmundsson J.","key":"S179383092250063XBIB017"},{"key":"S179383092250063XBIB018","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"S179383092250063XBIB019","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"S179383092250063XBIB020","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90143-0"},{"issue":"4","key":"S179383092250063XBIB021","first-page":"389","volume":"316","author":"Laroche P.","year":"1993","journal-title":"C. R. Acad. Sci., Ser. IIa: Sci. Terre Planets"},{"key":"S179383092250063XBIB022","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"first-page":"844","volume-title":"Proc. Twenty-Fourth Annual ACM-SIAM Symp. Discrete Algorithms, SODA 2013","author":"Mitchell J. S. B.","key":"S179383092250063XBIB023"},{"issue":"2","key":"S179383092250063XBIB024","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/S0921-8890(99)00020-2","volume":"28","author":"Moon I.","year":"1999","journal-title":"Rob. Auton. Syst."},{"issue":"4","key":"S179383092250063XBIB025","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/s00454-001-0047-6","volume":"26","author":"Moore C.","year":"2001","journal-title":"Discrete Comput. Geom."},{"first-page":"4242","volume-title":"Proc. 2002 IEEE Int. Conf. Robotics and Automation, ICRA 2002","author":"Murrieta-Cid R.","key":"S179383092250063XBIB026"},{"key":"S179383092250063XBIB027","volume-title":"Art Gallery Theorems and Algorithms","volume":"57","author":"O\u2019rourke J.","year":"1987"},{"key":"S179383092250063XBIB028","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"first-page":"656","volume-title":"Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms, SODA 2011","author":"Poloczek M.","key":"S179383092250063XBIB029"},{"first-page":"216","volume-title":"Proc. 10th Annual ACM Symp. Theory of Computing","author":"Schaefer T. J.","key":"S179383092250063XBIB030"},{"key":"S179383092250063XBIB031","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383092250063X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T05:24:05Z","timestamp":1675401845000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S179383092250063X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,22]]},"references-count":31,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1142\/S179383092250063X"],"URL":"https:\/\/doi.org\/10.1142\/s179383092250063x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2022,4,22]]},"article-number":"2250063"}}