ausblenden:
Schlagwörter:
Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS
Zusammenfassung:
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
$\Omega(d)\cap O(d^{3/2})$.
