Maximum Rectilinear Convex Subsets

Let P be a set of n points in the plane. We consider a variation of the classical Erdős-Szekeres problem, presenting efficient algorithms with (formula presented) running time and (formula presented) space complexity that compute: (1) A subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P, (2) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P and its interior contains no element of P, (3) a subset S of P such that the rectilinear convex hull of S has maximum area and its interior contains no element of P, and (4) when each point of P is assigned a weight, positive or negative, a subset S of P that maximizes the total weight of the points in the rectilinear convex hull of S. © 2019, Springer Nature Switzerland AG.