×

Online search for a hyperplane in high-dimensional Euclidean space. (English) Zbl 1515.68329

Summary: 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})\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angelopoulos, Spyros; Dürr, Christoph; Jin, Shendan, Best-of-two-worlds analysis of online search, (International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 126 (2019)), Article 7 pp. · Zbl 1510.68120
[2] Antoniadis, Antonios; Fleszar, Krzysztof; Hoeksma, Ruben; Schewior, Kevin, A PTAS for Euclidean TSP with hyperplane neighborhoods, ACM Trans. Algorithms, 16, 3, Article 38 pp. (2020) · Zbl 1484.68269
[3] Baeza-Yates, Ricardo A.; Culberson, Joseph C.; Rawlins, Gregory J. E., Searching in the plane, Inf. Comput., 106, 2, 234-252 (1993) · Zbl 0781.68044
[4] Beck, Anatole, On the linear search problem, Nav. Res. Logist., 2, 221-228 (1964) · Zbl 0168.39502
[5] Beck, Anatole; Newman, D. J., Yet more on the linear search problem, Isr. J. Math., 8, 4, 419-429 (1970) · Zbl 0209.20303
[6] Bellmann, Richard, An optimal search problem, SIAM Rev., 5, 274 (1963)
[7] Carlsson, Svante; Jonsson, Håkan; Nilsson, Bengt J., Finding the shortest watchman route in a simple polygon, Discrete Comput. Geom., 22, 3, 377-402 (1999) · Zbl 0939.68136
[8] Dror, Moshe; Efrat, Alon; Lubiw, Anna; Mitchell, Joseph S. B., Touring a sequence of polygons, (ACM Symposium on Theory of Computing (STOC) (2003), ACM), 473-482 · Zbl 1192.68354
[9] Dumitrescu, Adrian; Tóth, Csaba D., The traveling salesman problem for lines, balls, and planes, ACM Trans. Algorithms, 12, 3, Article 43 pp. (2016) · Zbl 1423.90220
[10] Finch, Steven R.; Zhu, Li-Yan, Searching for a shoreline (2005), arXiv preprint
[11] Gal, Shmuel, Search Games (1980), Academic Press · Zbl 0439.90102
[12] Ghomi, Mohammad; Wenk, James, Shortest closed curve to inspect a sphere, J. Reine Angew. Math., 2021, 781, 57-84 (2021) · Zbl 1482.53006
[13] Kao, Ming-Yang; Reif, John H.; Tate, Stephen R., Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, Inf. Comput., 131, 1, 63-79 (1996) · Zbl 0876.68030
[14] Karlin, Anna R.; Manasse, Mark S.; Rudolph, Larry; Sleator, Daniel Dominic, Competitive snoopy caching, Algorithmica, 3, 77-119 (1988) · Zbl 0645.68034
[15] Ore, Øystein, Note on Hamilton circuits, Am. Math. Mon., 67, 55 (1960) · Zbl 0089.39505
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.