Online Search for a Hyperplane in High-Dimensional Euclidean Space

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

Online Search for a Hyperplane in High-Dimensional Euclidean Space

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

Research output: Working paper

23 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 language	English
Publisher	arXiv.org
Publication status	Published - 9 Sep 2021

Keywords

cs.CG
cs.DS

Access to Document

2109.04340v1Submitted version, 1.35 MB

1 Article

Online search for a hyperplane in high-dimensional Euclidean space
Antoniadis, A., Hoeksma, R., Kisfaludi-Bak, S. & Schewior, K., Aug 2022, In: Information processing letters. 177, 4 p., 106262.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
1 Citation (Scopus)

16 Downloads (Pure)

Cite this

@techreport{456c96f38b4b4b279878996533f6225d,

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 $\Omega(d)\cap O(d^{3/2})$. ",

keywords = "cs.CG, cs.DS",

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

note = "Pages: 7, Figures: 2",

year = "2021",

month = sep,

day = "9",

language = "English",

publisher = "arXiv.org",

type = "WorkingPaper",

institution = "arXiv.org",

}

TY - UNPB

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

N1 - Pages: 7, Figures: 2

PY - 2021/9/9

Y1 - 2021/9/9

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 $\Omega(d)\cap 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 $\Omega(d)\cap O(d^{3/2})$.

KW - cs.CG

KW - cs.DS

M3 - Working paper

BT - Online Search for a Hyperplane in High-Dimensional Euclidean Space

PB - arXiv.org

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