Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Repository of the University of Ljubljana
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Advanced
New in RUL
About RUL
In numbers
Help
Sign in
Details
Searching in Euclidean spaces with predictions
ID
Cabello, Sergio
(
Author
),
ID
Giannopoulos, Panos
(
Author
)
PDF - Presentation file,
Download
(840,91 KB)
MD5: 494ED67441FCCB480C72505EA1E613D4
URL - Source URL, Visit
https://link.springer.com/article/10.1007/s00224-026-10291-w
Image galllery
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
UDC:
004.9
ISSN on article:
1432-4350
DOI:
10.1007/s00224-026-10291-w
COBISS.SI-ID:
292763139
Publication date in RUL:
28.09.2026
Views:
132
Downloads:
34
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Record is a part of a journal
Title:
Theory of computing systems
Publisher:
Springer
ISSN:
1432-4350
COBISS.SI-ID:
13043686
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