Online search for a hyperplane in high-dimensional Euclidean space

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

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
16 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 Ω(d)∩O(d 3/2).

Original languageEnglish
Article number106262
Number of pages4
JournalInformation processing letters
Volume177
Early online date24 Feb 2022
DOIs
Publication statusPublished - Aug 2022

Keywords

  • Sphere inspection
  • Online search problem
  • On-line algorithms
  • Computational geometry
  • Cow-path problem
  • UT-Hybrid-D

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