Online Search for a Hyperplane in High-Dimensional Euclidean Space

Antonios Antoniadis, Ruben Hoeksma, Sándor Kisfaludi-Bak, Kevin Schewior

Research output: Working paper

84 Downloads (Pure)

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})$.
Original languageEnglish
PublisherArXiv.org
Publication statusPublished - 9 Sept 2021

Keywords

  • cs.CG
  • cs.DS

Fingerprint

Dive into the research topics of 'Online Search for a Hyperplane in High-Dimensional Euclidean Space'. Together they form a unique fingerprint.

Cite this