Maximum rectilinear convex subsets
| Autor: | González-Aguilar, Hernán, Orden, David, Pérez-Lantero, Pablo, Rappaport, David, Seara, Carlos, Tejel, Javier, Urrutia, Jorge |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | SIAM Journal on Computing 50(1) (2021), 145-170 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1137/19M1303010 |
| Popis: | Let $P$ be a set of $n$ points in the plane. We consider a variation of the classical Erd\H{o}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$. 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. Comment: 27 pages, 15 figures, accepted version |
| Databáze: | arXiv |
| Externí odkaz: |
|