{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T04:25:55Z","timestamp":1766377555361},"reference-count":22,"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":[[2017,12]]},"abstract":"<jats:p> We study the General Position Subset Selection problem: Given a set of points in the plane, find a maximum-cardinality subset of points in general position. We prove that General Position Subset Selection is NP-hard, APX-hard, and present several fixed-parameter tractability results for the problem as well as a subexponential running time lower bound based on the Exponential Time Hypothesis. <\/jats:p>","DOI":"10.1142\/s021819591750008x","type":"journal-article","created":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T09:24:15Z","timestamp":1519118655000},"page":"277-296","source":"Crossref","is-referenced-by-count":19,"title":["Finding Points in General Position"],"prefix":"10.1142","volume":"27","author":[{"given":"Vincent","family":"Froese","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Germany"}]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[{"name":"School of Computing, DePaul University, Chicago, USA"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Germany"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, TU Berlin, Germany"}]}],"member":"219","published-online":{"date-parts":[[2018,2,19]]},"reference":[{"key":"S021819591750008XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"issue":"1","key":"S021819591750008XBIB003","first-page":"129","volume":"70","author":"van Bevern R.","year":"2014","journal-title":"Algorithmica"},{"key":"S021819591750008XBIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(95)00020-8"},{"key":"S021819591750008XBIB006","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"S021819591750008XBIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"S021819591750008XBIB008","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"S021819591750008XBIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90009-9"},{"key":"S021819591750008XBIB010","doi-asserted-by":"publisher","DOI":"10.1137\/0404019"},{"key":"S021819591750008XBIB011","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S021819591750008XBIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.042"},{"key":"S021819591750008XBIB013","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm053"},{"key":"S021819591750008XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00020-8"},{"key":"S021819591750008XBIB016","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1968-062-3"},{"key":"S021819591750008XBIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90043-6"},{"key":"S021819591750008XBIB018","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"S021819591750008XBIB019","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"S021819591750008XBIB021","doi-asserted-by":"publisher","DOI":"10.1145\/2832912"},{"key":"S021819591750008XBIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1108-4"},{"key":"S021819591750008XBIB024","doi-asserted-by":"publisher","DOI":"10.1137\/120897493"},{"key":"S021819591750008XBIB025","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-26.3.198"},{"key":"S021819591750008XBIB027","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","year":"2001"},{"key":"S021819591750008XBIB029","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819591750008X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:20:09Z","timestamp":1565126409000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819591750008X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":22,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2018,2,19]]},"published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1142\/S021819591750008X"],"URL":"https:\/\/doi.org\/10.1142\/s021819591750008x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}