Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali pa uporabite sodobnejši brskalnik.
Repozitorij Univerze v Ljubljani
Nacionalni portal odprte znanosti
Odprta znanost
DiKUL
slv
|
eng
Iskanje
Napredno
Novo v RUL
Kaj je RUL
V številkah
Pomoč
Prijava
Podrobno
Searching in Euclidean spaces with predictions
ID
Cabello, Sergio
(
Avtor
),
ID
Giannopoulos, Panos
(
Avtor
)
PDF - Predstavitvena datoteka,
prenos
(840,91 KB)
MD5: 494ED67441FCCB480C72505EA1E613D4
URL - Izvorni URL, za dostop obiščite
https://link.springer.com/article/10.1007/s00224-026-10291-w
Galerija slik
Izvleček
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$.
Jezik:
Angleški jezik
Ključne besede:
search games
,
predictions
,
distance
,
computational geometry
Vrsta gradiva:
Članek v reviji
Tipologija:
1.01 - Izvirni znanstveni članek
Organizacija:
FMF - Fakulteta za matematiko in fiziko
Status publikacije:
Objavljeno
Različica publikacije:
Objavljena publikacija
Leto izida:
2026
Št. strani:
27 str.
Številčenje:
Vol. 70, iss. 3, art. 49
PID:
20.500.12556/RUL-188803
UDK:
004.9
ISSN pri članku:
1432-4350
DOI:
10.1007/s00224-026-10291-w
COBISS.SI-ID:
292763139
Datum objave v RUL:
28.09.2026
Število ogledov:
136
Število prenosov:
34
Metapodatki:
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Kopiraj citat
Objavi na:
Gradivo je del revije
Naslov:
Theory of computing systems
Založnik:
Springer
ISSN:
1432-4350
COBISS.SI-ID:
13043686
Licence
Licenca:
CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
Povezava:
http://creativecommons.org/licenses/by/4.0/deed.sl
Opis:
To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
Sekundarni jezik
Jezik:
Slovenski jezik
Ključne besede:
igre
,
napovedi
,
računska geometrija
Projekti
Financer:
ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:
P1-0297
Naslov:
Teorija grafov
Financer:
ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:
J1-2452
Naslov:
Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Financer:
ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:
N1-0218
Naslov:
Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov
Financer:
ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:
N1-0285
Naslov:
Metrični problemi v grafih in hipergrafih
Financer:
ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:
J1-70045
Naslov:
Splošna lega in vidnost v teoriji grafov
Financer:
EC - European Commission
Številka projekta:
101071836
Naslov:
KARST: Predicting flow and transport in complex Karst systems
Akronim:
KARST
Financer:
EC - European Commission
Številka projekta:
882971
Naslov:
From Geometry to Combinatorics and Back: Escaping the Curse of Dimensionality
Akronim:
GeoScape
Podobna dela
Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:
Nazaj