summarized by saying that the problem is APX-hard. If the largest subset has a solution with the non-constant approximation ratio can be obtained by a greedy algorithm that simply chooses points one at a time until all remaining points lie on lines through pairs of chosen points. One can get a finer-grained understanding of the running time of algorithms for finding the exact optimal solution by using parameterized complexity, in which algorithms are analyzed not only in terms of the input size, but in terms of other parameters of the input. In this case, for inputs whose largest general position subset has it can be found in an amount of time that is an exponential function of multiplied by a polynomial in the input with the exponent of the polynomial not depending Problems with this kind of time bound are called fixed-parameter tractable. For point sets having at most points per line, with there exist general-position subsets of size nearly proportional The example of the grid shows that this bound cannot be significantly improved. The proof of existence of these large general-position subsets can be converted into a polynomial-time algorithm for finding a general-position subset of size matching the existence bound, using an algorithmic technique known as entropy compression. Greedy placement Repeating a suggestion of , Martin Gardner asked for the smallest subset of an grid that cannot be extended: it has no three points in a line, but every proper superset has three in a line. Equivalently, this is the smallest set that could be produced by a greedy algorithm that tries to solve the no-three-in-line problem by placing points one at a time until it gets stuck. If only axis-parallel and diagonal lines are considered, then every such set has at least points. However, less is known about the version of the problem where all lines are considered: every greedy placement includes at least points before getting stuck, but nothing better than the trivial upper bound is known. Higher dimensions Non-collinear sets of points in the three-dimensional grid were considered by . They proved that the maximum number of points in the grid with no three points collinear Similarly to Erdős's 2D construction, this can be accomplished by using points where is a prime congruent to . Just as the original no-three-in-line problem can be used for two-dimensional graph drawing, one can use this three-dimensional solution to draw