Given a set of points in the 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 NP-complete and APX-hard, and the best approximation ratio known is \(\varOmega \left( \textsf {OPT}^{-1/2}\right) =\varOmega (n^{-1/2})\) . Here we obtain better approximations in two 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 distances in P is of the order of \(\varTheta (\sqrt{n})\) . (II) An \(\varOmega \left( (\log {n})^{-1/2}\right) \) -approximation for the case where the input set is the set of vertices of a generic n-line arrangement, i.e., one with \(\varOmega (n^2)\) vertices. The scenario in (I) is a special case of that in (II). Our approximations rely on probabilistic methods and results from incidence geometry.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

General Position Subset Selection in Line Arrangements

  • Adrian Dumitrescu

摘要

Given a set of points in the 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 NP-complete and APX-hard, and the best approximation ratio known is \(\varOmega \left( \textsf {OPT}^{-1/2}\right) =\varOmega (n^{-1/2})\) . Here we obtain better approximations in two 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 distances in P is of the order of \(\varTheta (\sqrt{n})\) . (II) An \(\varOmega \left( (\log {n})^{-1/2}\right) \) -approximation for the case where the input set is the set of vertices of a generic n-line arrangement, i.e., one with \(\varOmega (n^2)\) vertices. The scenario in (I) is a special case of that in (II). Our approximations rely on probabilistic methods and results from incidence geometry.