Maximum rectilinear convex subsets
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915067226750976 |
|---|---|
| author | González-Aguilar, Hernán Orden, David Pérez-Lantero, Pablo Rappaport, David Seara, Carlos Tejel, Javier Urrutia, Jorge |
| author_facet | González-Aguilar, Hernán Orden, David Pérez-Lantero, Pablo Rappaport, David Seara, Carlos Tejel, Javier Urrutia, Jorge |
| contents | 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$.
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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1907_07441 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Maximum rectilinear convex subsets González-Aguilar, Hernán Orden, David Pérez-Lantero, Pablo Rappaport, David Seara, Carlos Tejel, Javier Urrutia, Jorge Computational Geometry Discrete Mathematics 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$. 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. |
| title | Maximum rectilinear convex subsets |
| topic | Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/1907.07441 |