An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915073870528512 |
|---|---|
| author | Flores-Peñaloza, David Lopez, Mario A. Marín, Nestaly Orden, David |
| author_facet | Flores-Peñaloza, David Lopez, Mario A. Marín, Nestaly Orden, David |
| contents | Let $P$ be a $k$-colored set of $n$ points in the plane, $4 \leq k \leq n$. We study the problem of deciding if $P$ contains a subset of four points of different colors such that its Rectilinear Convex Hull has positive area. We show this problem to be equivalent to deciding if there exists a point $c$ in the plane such that each of the open quadrants defined by $c$ contains a point of $P$, each of them having a different color. We provide an $O(n \log n)$-time algorithm for this problem, where the hidden constant does not depend on $k$; then, we prove that this problem has time complexity $Ω(n \log n)$ in the algebraic computation tree model. No general position assumptions for $P$ are required. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06376 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets Flores-Peñaloza, David Lopez, Mario A. Marín, Nestaly Orden, David Computational Geometry Combinatorics 68U05 (Primary), 68R05 (Secondary) G.2.1; F.2.2 Let $P$ be a $k$-colored set of $n$ points in the plane, $4 \leq k \leq n$. We study the problem of deciding if $P$ contains a subset of four points of different colors such that its Rectilinear Convex Hull has positive area. We show this problem to be equivalent to deciding if there exists a point $c$ in the plane such that each of the open quadrants defined by $c$ contains a point of $P$, each of them having a different color. We provide an $O(n \log n)$-time algorithm for this problem, where the hidden constant does not depend on $k$; then, we prove that this problem has time complexity $Ω(n \log n)$ in the algebraic computation tree model. No general position assumptions for $P$ are required. |
| title | An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets |
| topic | Computational Geometry Combinatorics 68U05 (Primary), 68R05 (Secondary) G.2.1; F.2.2 |
| url | https://arxiv.org/abs/2404.06376 |