Right angle free subsets in the plane

Abstract

In this paper we investigate the complexity of finding maximum right angle free subsets of a given set of points in the plane. For a set of rational points P in the plane, the right angle number ρ(P) (respectively rectilinear right angle numberρR(P)) of P is the cardinality of a maximum subset of P, no three members of which form a right angle triangle (respectively a right angle triangle with its side or base parallel to the x-axis). It is shown that both parameters are NP-hard to compute. The latter problem is also shown to be equivalent to finding a minimum dominating set in a bipartite graph. This is used to show that there is a polynomial algorithm for computing ρR(P) when P is a horizontally-convex subset of the lattice ℤ × ℤ (P is horizontally-convex if for any pair of points in P which lie on a horizontal line, every lattice point between them is also in P). We then show that this algorithm yields a 1/2-approximate algorithm for the right angle number of a convex subregion of the lattice. © 1995 Springer-Verlag.