Online search for a hyperplane in high-dimensional Euclidean space

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

doi:10.1016/j.ipl.2022.106262

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 journal › Article › Academic › peer-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 language	English
Article number	106262
Number of pages	4
Journal	Information processing letters
Volume	177
Early online date	24 Feb 2022
DOIs	https://doi.org/10.1016/j.ipl.2022.106262
Publication status	Published - Aug 2022

Keywords

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

Access to Document

10.1016/j.ipl.2022.106262Licence: CC BY

Online search forFinal published version, 315 KBLicence: CC BY

1 Citations
1 Working paper

Online Search for a Hyperplane in High-Dimensional Euclidean Space
Antoniadis, A., Hoeksma, R., Kisfaludi-Bak, S. & Schewior, K., 9 Sep 2021, arXiv.org.
Research output: Working paper

File

Cite this

@article{20080913d4c841d49a89de4bf6be36ec,

title = "Online search for a hyperplane in high-dimensional Euclidean space",

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). ",

keywords = "Sphere inspection, Online search problem, On-line algorithms, Computational geometry, Cow-path problem, UT-Hybrid-D",

author = "Antonios Antoniadis and Ruben Hoeksma and S{\'a}ndor Kisfaludi-Bak and Kevin Schewior",

year = "2022",

month = aug,

doi = "10.1016/j.ipl.2022.106262",

language = "English",

volume = "177",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

}

TY - JOUR

T1 - Online search for a hyperplane in high-dimensional Euclidean space

AU - Antoniadis, Antonios

AU - Hoeksma, Ruben

AU - Kisfaludi-Bak, Sándor

AU - Schewior, Kevin

PY - 2022/8

Y1 - 2022/8

N2 - 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).

AB - 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).

KW - Sphere inspection

KW - Online search problem

KW - On-line algorithms

KW - Computational geometry

KW - Cow-path problem

KW - UT-Hybrid-D

U2 - 10.1016/j.ipl.2022.106262

DO - 10.1016/j.ipl.2022.106262

M3 - Article

VL - 177

JO - Information processing letters

JF - Information processing letters

SN - 0020-0190

M1 - 106262

ER -

Online search for a hyperplane in high-dimensional Euclidean space

Abstract

Keywords

Access to Document

Fingerprint

Research output

Online Search for a Hyperplane in High-Dimensional Euclidean Space

Cite this