Online search for a hyperplane in high-dimensional Euclidean space
Antonios Antoniadis, Ruben Hoeksma, Sándor Kisfaludi-Bak, Kevin Schewior · Information Processing Letters · 2022
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(d3/2).