Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Maximum Rectilinear Convex Subsets
verfasst von : Hernán González-Aguilar, David Orden, Pablo Pérez-Lantero, David Rappaport, Carlos Seara, Javier Tejel, Jorge Urrutia
Erschienen in: Fundamentals of Computation Theory
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \(O(n^3)\) running time and \(O(n^2)\) 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.