TY - JOUR
T1 - Online search for a hyperplane in high-dimensional Euclidean space
AU - Antoniadis, Antonios
AU - Hoeksma, Ruben
AU - Kisfaludi-Bak, Sándor
AU - Schewior, Kevin
N1 - Funding Information:
We thank Paula Roth for helpful discussions.
Publisher Copyright:
© 2022 The Author(s)
PY - 2022/8
Y1 - 2022/8
N2 - We consider the online search problem in which a server starting at the origin of a d-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the d-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in Ω(d) ∩O (d 3/2).
AB - We consider the online search problem in which a server starting at the origin of a d-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the d-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in Ω(d) ∩O (d 3/2).
KW - Computational geometry
KW - Cow-path problem
KW - On-line algorithms
KW - Online search problem
KW - Sphere inspection
UR - http://www.scopus.com/inward/record.url?scp=85125462458&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2022.106262
DO - 10.1016/j.ipl.2022.106262
M3 - Article
AN - SCOPUS:85125462458
VL - 177
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
M1 - 106262
ER -