Right angle free subsets in the plane (Q1895818): Difference between revisions

Let \(P\) be a set of points in the plane. A subset \(S\) of \(P\) is called right angle free if no three points of \(S\) form the vertices of a right angle triangle. The authors consider the following computational decision problem, called RAF: Given an integer \(k\) and a finite set \(P\) of rational points in the plane, determine whether \(P\) contains a right angle free subset with at least \(k\) elements. This problem is shown to be (strongly) NP-complete, as well as the corresponding problem RRAF, where only triangles with a horizontal and a vertical side are taken into account. The proofs work by reduction to graph-theoretical problems which are known to be NP-complete: the stability number of a general graph and the domination number of a bipartite graph. On the other hand, for the case that \(P\) is a horizontally convex subset of the lattice \(\mathbb{Z}^2\), a polynomial algorithm for RRAF is derived. This leads to a (1/2)- approximate algorithm for RAF in this case.