{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:19:55Z","timestamp":1760059195597,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Given a set of n points in a plane, the General Position Subset Selection problem is that of finding a maximum-size subset of points in general position, i.e., with no three points collinear. The problem is known to be hard computationally, and the best approximation ratio known is \u03a9(n\u22121\/2). Here, we obtain better approximations in three special cases: (I) a constant-factor approximation for the case where the input set consists of lattice points and is dense, which means that the ratio between the maximum and the minimum distance in P is of the order of \u0398(n); (II) an \u03a9(logn)\u22121\/2-approximation for the case where the input set is the set of vertices of a genericn-line arrangement, i.e., one with \u03a9(n2) vertices; and (III) an \u03a9(logn)\u22121\/2-approximation for the case where the input set has at most O(n) points collinear and can be covered by O(n) lines. The scenario in (I) is a special case of that in (II). Our approximations rely on probabilistic methods and results from incidence geometry.<\/jats:p>","DOI":"10.3390\/a18060315","type":"journal-article","created":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T05:52:52Z","timestamp":1748325172000},"page":"315","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["General Position Subset Selection in Line Arrangements"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1118-0321","authenticated-orcid":false,"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"Algoresearch L.L.C., Milwaukee, WI 53217, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,5,27]]},"reference":[{"key":"ref_1","unstructured":"Dudeney, H. (1917). A puzzle with pawns. Amusements in Mathematics, Nelson."},{"key":"ref_2","unstructured":"Bra\u00df, P., Moser, W., and Pach, J. (2005). Research Problems in Discrete Geometry, Springer."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1137\/120897493","article-title":"On the general position subset selection problem","volume":"27","author":"Payne","year":"2013","journal-title":"SIAM J. Discret. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02579194","article-title":"Extremal problems in discrete geometry","volume":"3","author":"Trotter","year":"1983","journal-title":"Combinatorica"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Pach, J., and Agarwal, P. (1995). Combinatorial Geometry, Wiley-Interscience.","DOI":"10.1002\/9781118033203"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1017\/S0963548397002976","article-title":"Crossing numbers and hard Erd\u0151s problems in discrete geometry","volume":"6","year":"1997","journal-title":"Comb. Probab. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"946","DOI":"10.1016\/j.ejc.2007.11.021","article-title":"Distributions of points in the unit square and large k-gons","volume":"29","author":"Lefmann","year":"2008","journal-title":"Eur. J. Comb."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Tao, T., and Vu, V. (2006). Additive Combinatorics, Cambridge University Press. Cambridge Studies in Advanced Mathematics, 105.","DOI":"10.1017\/CBO9780511755149"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0012-365X(72)90084-2","article-title":"Tur\u00e1n\u2019s theorem for k-graphs","volume":"2","author":"Spencer","year":"1972","journal-title":"Discret. Math."},{"key":"ref_10","unstructured":"Cao, C. (2012). Study on Two Optimization Problems: Line Cover and Maximum Genus Embedding. [Master\u2019s Thesis, Texas A&M University]."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Eppstein, D. (2018). Forbidden Configurations in Discrete Geometry, Cambridge University Press.","DOI":"10.1017\/9781108539180"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1142\/S021819591750008X","article-title":"Finding points in general position","volume":"27","author":"Froese","year":"2017","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Williamson, D., and Shmoys, D. (2011). The Design of Approximation Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511921735"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF02187831","article-title":"Convex independent sets and 7-holes in restricted planar point sets","volume":"7","author":"Valtr","year":"1992","journal-title":"Discret. Comput. Geom."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1007\/s00454-019-00080-3","article-title":"Dense point sets with many halving lines","volume":"64","year":"2020","journal-title":"Discret. Comput. Geom."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02579184","article-title":"On the lattice property of the plane and some problems of Dirac, Motzkin and Erd\u0151s in combinatorial geometry","volume":"3","author":"Beck","year":"1983","journal-title":"Combinatorica"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J. (2002). Lectures on Discrete Geometry, Springer.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1016\/j.comgeo.2015.06.006","article-title":"On the approximability of covering points by lines and related problems","volume":"48","author":"Dumitrescu","year":"2015","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_19","first-page":"193","article-title":"A note on colouring the plane grid","volume":"13","author":"Wood","year":"2004","journal-title":"Geombinatorics"},{"key":"ref_20","first-page":"177","article-title":"On the interval containing at least one prime number","volume":"28","author":"Nagura","year":"1952","journal-title":"Proc. Jpn. Acad."},{"key":"ref_21","first-page":"198","article-title":"Appendix, in Klaus F. Roth, On a problem of Heilbronn","volume":"1","author":"Erdos","year":"1951","journal-title":"J. Lond. Math. Soc."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal","year":"2004","journal-title":"Ann. Math."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Motwani, R., and Raghavan, P. (1995). Randomized Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1112\/plms\/83.3.532","article-title":"The difference between consecutive primes, II","volume":"83","author":"Baker","year":"2001","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_25","unstructured":"Alon, N., and Spencer, J. (2016). The Probabilistic Method, Wiley. [4th ed.]."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01202795","article-title":"A note on arrays of dots with distinct slopes","volume":"13","author":"Zhang","year":"1993","journal-title":"Combinatorica"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer. [3rd ed.].","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref_28","unstructured":"Balogh, J., Clemen, F.C., Dumitrescu, A., and Liu, D. (2024). Subset selection problems in planar point sets. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/6\/315\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:41:02Z","timestamp":1760031662000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/6\/315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":28,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["a18060315"],"URL":"https:\/\/doi.org\/10.3390\/a18060315","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,5,27]]}}}