Searching on a line: a complete characterization of the optimal solution. (English) Zbl 1312.68210
Summary: We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance \(D\) that separates the initial position of the searcher from the target. Prior to this work, only asymptotic bounds were known for the optimal competitive ratio achievable by any search strategy in the worst case. We present the first tight bounds on the exact optimal competitive ratio achievable, parameterized in terms of the given bounds on \(D\), along with an optimal search strategy that achieves this competitive ratio. We prove that this optimal strategy is unique. We characterize the conditions under which an optimal strategy can be computed exactly and, when it cannot, we explain how numerical methods can be used efficiently. In addition, we answer several related open questions, including the maximal reach problem, and we discuss how to generalize these results to \(m\) rays, for any \(m \geq 2\).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68W27 | Online algorithms; streaming algorithms |
References:
| [1] | Alpern, S.; Baston, V.; Essegaier, S., Rendezvous search on a graph, J. Appl. Probab., 36, 1, 223-231 (1999) · Zbl 0940.90038 |
| [2] | Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous, Internat. Ser. Oper. Res. Management Sci. (2003), Kluwer Academic Publishers · Zbl 1034.91017 |
| [3] | Alpern, S.; Fokkink, R.; Gasieniec, L.; Lindelauf, R.; Subrahmanian, V. S., Search Theory: A Game Theoretic Perspective (2013), Springer · Zbl 1263.91001 |
| [4] | Baeza-Yates, R. A.; Culberson, J. C.; Rawlins, G. J.E., Searching in the plane, Inf. Comput., 106, 2, 234-252 (1993) · Zbl 0781.68044 |
| [5] | Bellman, R., Minimization problem, Bull. Amer. Math. Soc., 62, 3, 270 (1956) |
| [6] | Bender, M. A.; Fernández, A.; Ron, D.; Sahai, A.; Vadhan, S. P., The power of a pebble: exploring and mapping directed graphs, (STOC (1998)), 269-278 · Zbl 1027.68652 |
| [7] | Bose, P.; De Carufel, J.-L.; Durocher, S., Revisiting the problem of searching on a line, (ESA. ESA, LNCS, vol. 8125 (2013)), 205-216 · Zbl 1394.68166 |
| [8] | Collins, A.; Czyzowicz, J.; Gasieniec, L.; Labourel, A., Tell me where I am so I can meet you sooner, (ICALP. ICALP, LNCS, vol. 6199 (2010)), 502-514 · Zbl 1288.68214 |
| [9] | Czyzowicz, J.; Ilcinkas, D.; Labourel, A.; Pelc, A., Asynchronous deterministic rendezvous in bounded terrains, Theoret. Comput. Sci., 412, 50, 6926-6937 (2011) · Zbl 1227.68107 |
| [10] | Dieudonné, Y.; Pelc, A., Anonymous meeting in networks, (SODA (2013)), 737-747 · Zbl 1421.68118 |
| [11] | Hammar, M.; Nilsson, B. J.; Schuierer, S., Parallel searching on m rays, Comput. Geom., 18, 3, 125-139 (2001) · Zbl 0976.68045 |
| [12] | Hipke, C. A.; Icking, C.; Klein, R.; Langetepe, E., How to find a point on a line within a fixed distance, Discrete Appl. Math., 93, 1, 67-73 (1999) · Zbl 0942.68131 |
| [13] | Hoggatt, V.; Long, C., Divisibility properties of generalized Fibonacci polynomials, Fibonacci Quart., 12, 2, 113-120 (1974) · Zbl 0284.10003 |
| [14] | Koutsoupias, E.; Papadimitriou, C. H.; Yannakakis, M., Searching a fixed graph, (ICALP (1996)), 280-289 · Zbl 1045.90532 |
| [15] | López-Ortiz, A.; Schuierer, S., The ultimate strategy to search on m rays?, Theoret. Comput. Sci., 261, 2, 267-295 (2001) · Zbl 0972.68053 |
| [16] | De Marco, G.; Gargano, L.; Kranakis, E.; Krizanc, D.; Pelc, A.; Vaccaro, U., Asynchronous deterministic rendezvous in graphs, Theoret. Comput. Sci., 355, 3, 315-326 (2006) · Zbl 1088.68140 |
| [17] | McNamee, J. M., Numerical Methods for Roots of Polynomials, Part I (2007), Elsevier · Zbl 1143.65002 |
| [18] | McNamee, J. M.; Pan, V. Y., Numerical Methods for Roots of Polynomials, Part II (2013), Elsevier · Zbl 1279.65053 |
| [19] | Preparata, F. P.; Shamos, M. I., Computational Geometry - An Introduction (1985), Springer · Zbl 0759.68037 |
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.
