About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Graphs and Combinatorics
Paper
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.