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 › Scientific › peer-review

3 Citations (Scopus)

69 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
DOIs	https://doi.org/10.1016/j.ipl.2022.106262
Publication status	Published - Aug 2022
MoE publication type	A1 Journal article-refereed

Funding

We thank Paula Roth for helpful discussions.

Keywords

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

Access to Document

10.1016/j.ipl.2022.106262Licence: CC BY

SCI_Antoniadis_etal_Online_search_for_a_hyperplane_Information_Processing_Letters_2022Final published version, 325 KBLicence: CC BY

Cite this

@article{ab72b622808e4e9b928c41846574fe63,

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 = "Computational geometry, Cow-path problem, On-line algorithms, Online search problem, Sphere inspection",

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

note = "Funding Information: We thank Paula Roth for helpful discussions. Publisher Copyright: {\textcopyright} 2022 The Author(s)",

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 - Computational geometry

KW - Cow-path problem

KW - On-line algorithms

KW - Online search problem

KW - Sphere inspection

UR - https://www.scopus.com/pages/publications/85125462458

U2 - 10.1016/j.ipl.2022.106262

DO - 10.1016/j.ipl.2022.106262

M3 - Article

AN - SCOPUS:85125462458

SN - 0020-0190

VL - 177

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106262

ER -

Online search for a hyperplane in high-dimensional Euclidean space

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this