English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Online Search for a Hyperplane in High-Dimensional Euclidean Space

MPS-Authors
/persons/resource/persons252857

Kisfaludi-Bak,  Sándor
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2109.04340.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Antoniadis, A., Hoeksma, R., Kisfaludi-Bak, S., & Schewior, K. (2021). Online Search for a Hyperplane in High-Dimensional Euclidean Space. Retrieved from https://arxiv.org/abs/2109.04340.


Cite as: https://hdl.handle.net/21.11116/0000-0009-B814-1
Abstract
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})$.