| dc.creator | Pérez-Lantero, Pablo | |
| dc.creator | Seara, Carlos | |
| dc.date | 2022-05-20T20:45:19Z | |
| dc.date | 2022-06-18T20:37:20Z | |
| dc.date | 2022-05-20T20:45:19Z | |
| dc.date | 2022-06-18T20:37:20Z | |
| dc.date | June28 | |
| dc.date | 2017 | |
| dc.date | 2017 | |
| dc.date | June26 | |
| dc.date.accessioned | 2023-08-22T09:43:46Z | |
| dc.date.available | 2023-08-22T09:43:46Z | |
| dc.identifier | 1160543 | |
| dc.identifier | https://hdl.handle.net/10533/253919 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/8337403 | |
| dc.description | Given disjoint finite point sets R and B in the plane,
where the elements of R are colored red and the elements
of B are colored blue, the maximum box problem
asks for an axis-aligned rectangle (i.e. box) containing
the maximum number of red points and no
blue point. We consider this problem when the input
is imprecise. That is, we consider that each point of
R∪B has its own and independent probability of being
present in the final random point set. We prove
that, given any k ≥ 2, computing the probability that
there exists a box containing at least k red points and
no blue point is #P-hard, as well as the problem of
computing the expectation of the maximum number
of red points that can be covered with a box not containing
any blue point. We complement these results
with a polytime algorithm computing the probability
that there exists a box containing exactly two red
points, no blue point, and a given point of the plane. | |
| dc.description | FONDECYT | |
| dc.description | FONDECYT | |
| dc.language | eng | |
| dc.relation | instname: ANID | |
| dc.relation | reponame: Repositorio Digital RI2.0 | |
| dc.relation | Spanish Meeting on Computational Geometry | |
| dc.relation | 17° | |
| dc.rights | http://creativecommons.org/licenses/by/3.0/cl/ | |
| dc.title | Maximum Box Problem on Probabilistic Points | |
| dc.type | info:eu-repo/semantics/lecture | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
| dc.coverage | Alicante | |
