Details

Searching in Euclidean spaces with predictions
ID Cabello, Sergio (Author), ID Giannopoulos, Panos (Author)

.pdfPDF - Presentation file, Download (840,91 KB)
MD5: 494ED67441FCCB480C72505EA1E613D4
URLURL - Source URL, Visit https://link.springer.com/article/10.1007/s00224-026-10291-w This link opens in a new window

Abstract
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 $|pt|\le \lambda (p) \le c\cdot |pt|$, where $c \ge 1$ is a fixed constant, $t$ is the position of the target, and $|pt|$ is the Euclidean distance of $p$ to $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 $O(c^d)$-competitive ratio, even when the constant c is unknown. We also give a lower bound of roughly $(c/4)^{d-1}$ on the competitive ratio of any search strategy in ${\mathbb R}^d$, assuming that $c\ge 4$.

Language:English
Keywords:search games, predictions, distance, computational geometry
Work type:Article
Typology:1.01 - Original Scientific Article
Organization:FMF - Faculty of Mathematics and Physics
Publication status:Published
Publication version:Version of Record
Year:2026
Number of pages:27 str.
Numbering:Vol. 70, iss. 3, art. 49
PID:20.500.12556/RUL-188803 This link opens in a new window
UDC:004.9
ISSN on article:1432-4350
DOI:10.1007/s00224-026-10291-w This link opens in a new window
COBISS.SI-ID:292763139 This link opens in a new window
Publication date in RUL:28.09.2026
Views:132
Downloads:34
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Record is a part of a journal

Title:Theory of computing systems
Publisher:Springer
ISSN:1432-4350
COBISS.SI-ID:13043686 This link opens in a new window

Licences

License:CC BY 4.0, Creative Commons Attribution 4.0 International
Link:http://creativecommons.org/licenses/by/4.0/
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

Language:Slovenian
Keywords:igre, napovedi, računska geometrija

Projects

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-2452
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0218
Name:Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0285
Name:Metrični problemi v grafih in hipergrafih

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-70045
Name:Splošna lega in vidnost v teoriji grafov

Funder:EC - European Commission
Project number:101071836
Name:KARST: Predicting flow and transport in complex Karst systems
Acronym:KARST

Funder:EC - European Commission
Project number:882971
Name:From Geometry to Combinatorics and Back: Escaping the Curse of Dimensionality
Acronym:GeoScape

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back