Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2505.04617 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913825718009856 |
|---|---|
| author | Mishra, Naman Sreeramji, K S |
| author_facet | Mishra, Naman Sreeramji, K S |
| contents | Given two points $p, q \in \mathbb R^d$, we say that $p$ dominates $q$ and write $p \succ q$ if each coordinate of $p$ is larger than the corresponding coordinate of $q$. That is, if $p = (p^{(1)}, p^{(2)}, \ldots, p^{(d)})$ and $q = (q^{(1)}, q^{(2)}, \ldots, q^{(d)})$, $p \succ q$ if and only if $p^{(i)} > q^{(i)}$ for all $1 \le i \le d$.
For example, $p$ and $q$ could represent various ratings for $2$ restaurants, based on different metrics like taste, affordability, ratings on different platforms, et cetera. $p \succ q$ then means that the first restaurant outperformed the second on each metric.
Given a list of restaurants and their rating, we solve the problem of determining, for each restaurant, the closest restaurant to it that dominates it. We improve upon the algorithm under some assumptions towards the end. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04617 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Report on Nearest Dominating Point Queries Mishra, Naman Sreeramji, K S Computational Geometry Given two points $p, q \in \mathbb R^d$, we say that $p$ dominates $q$ and write $p \succ q$ if each coordinate of $p$ is larger than the corresponding coordinate of $q$. That is, if $p = (p^{(1)}, p^{(2)}, \ldots, p^{(d)})$ and $q = (q^{(1)}, q^{(2)}, \ldots, q^{(d)})$, $p \succ q$ if and only if $p^{(i)} > q^{(i)}$ for all $1 \le i \le d$. For example, $p$ and $q$ could represent various ratings for $2$ restaurants, based on different metrics like taste, affordability, ratings on different platforms, et cetera. $p \succ q$ then means that the first restaurant outperformed the second on each metric. Given a list of restaurants and their rating, we solve the problem of determining, for each restaurant, the closest restaurant to it that dominates it. We improve upon the algorithm under some assumptions towards the end. |
| title | Report on Nearest Dominating Point Queries |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2505.04617 |