2025/05/07 by Mishra, Naman, K S Sreeramji, Sreeramji, K S
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2505.04617
openalex publication_date 2025/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two points p, q ∈ \mathbb Rd, 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), …, p(d)) and q = (q(1), q(2), …, q(d)), p \succ q if and only if p(i) > q(i) for all 1 ≤ i ≤ 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.