Maximum rectilinear convex subsets

Gonzalez-Aguilar, H. ; Orden, D. ; Perez-Lantero, P. ; Rappaport, D. ; Seara, C. ; Tejel, J. (Universidad de Zaragoza) ; Urrutia, J.

Resumen: Let P be a set of n points in the plane. We consider a variation of the classical Erd\H os-Szekeres problem, presenting efficient algorithms with O(n3) running time and O(n2) 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. We also revisit the problems of computing a maximum area orthoconvex polygon and computing a maximum area staircase polygon, amidst a point set in a rectangular domain. We obtain new and simpler algorithms to solve both problems with the same complexity as in the state of the art.

Idioma: Inglés

DOI: 10.1137/19M1303010

Año: 2021

Publicado en: SIAM JOURNAL ON COMPUTING 50, 1 (2021), 145-170
ISSN: 0097-5397

Factor impacto JCR: 1.475 (2021)

Categ. JCR: MATHEMATICS, APPLIED rank: 119 / 267 = 0.446 (2021) - Q2 - T2
Categ. JCR: COMPUTER SCIENCE, THEORY & METHODS rank: 65 / 111 = 0.586 (2021) - Q3 - T2

Factor impacto CITESCORE: 4.4 - Mathematics (Q1) - Computer Science (Q2)

Factor impacto SCIMAGO: 2.349 - Mathematics (miscellaneous) (Q1) - Computer Science (miscellaneous) (Q1)

Financiación: info:eu-repo/grantAgreement/ES/DGA/E41-17R
Financiación: info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT
Financiación: info:eu-repo/grantAgreement/ES/MICIU-AEI/PID2019-104129GB-I00-AEI-10.13039-501100011033
Financiación: info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2015-63791-R

Tipo y forma: Article (Published version)

Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)