Searching in Euclidean Spaces with Predictions
<|reference_start|>Searching in Euclidean Spaces with Predictions: We study the problem of searching for a target at some unknown location in $\mathbb{R}^d$ when additional information regarding the position of the target is available in the form of predictions. In our setting, predictions come as approximate distances to the target: for each point $p\in \mathbb{R}^d$ that the searcher visits, we obtain a value $\lambda(p)$ such that $|p\mathbf{t}|\le \lambda(p) \le c\cdot |p\mathbf{t}|$, where $c\ge 1$ is a fixed constant, $\mathbf{t}$ is the position of the target, and $|p\mathbf{t}|$ is the Euclidean distance of $p$ to $\mathbf{t}$. The cost of the search is the length of the path followed by the searcher. Our main positive result is a strategy that achieves $(12c)^{d+1}$-competitive ratio, even when the constant $c$ is unknown. We also give a lower bound of roughly $(c/16)^{d-1}$ on the competitive ratio of any search strategy in $\mathbb{R}^d$.<|reference_end|>
@article{cabello2024searching,
    title={Searching in Euclidean Spaces with Predictions},
    author={Sergio Cabello and Panos Giannopoulos},
    journal={arXiv preprint arXiv:2408.04964},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04964},
    primaryClass={cs.CG}
}