Abstract
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, parametrized in terms of the given range for D, along with an optimal search strategy that achieves this competitive ratio. We prove that this optimal strategy is unique and that it cannot be computed exactly in general. 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 and we discuss how to generalize these results to m rays, for any m ≥ 2.
This research has been partially funded by NSERC and FQRNT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpern, S., Baston, V., Essegaier, S.: Rendezvous search on a graph. J. App. Prob. 36(1), 223–231 (1999)
Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. International Series in Operations Research & Management Science. Kluwer Academic Publishers (2003)
Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. & Comp. 106(2), 234–252 (1993)
Bellman, R.: Minimization problem. Bull. AMS 62(3), 270 (1956)
Bender, M.A., Fernández, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: Exploring and mapping directed graphs. In: STOC, pp. 269–278 (1998)
Collins, A., Czyzowicz, J., Gąsieniec, L., Labourel, A.: Tell me where I am so I can meet you sooner. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 502–514. Springer, Heidelberg (2010)
Czyzowicz, J., Ilcinkas, D., Labourel, A., Pelc, A.: Asynchronous deterministic rendezvous in bounded terrains. Theor. Comp. Sci. 412(50), 6926–6937 (2011)
Dieudonné, Y., Pelc, A.: Anonymous meeting in networks. In: SODA, pp. 737–747 (2013)
Hammar, M., Nilsson, B.J., Schuierer, S.: Parallel searching on m rays. Comput. Geom. 18(3), 125–139 (2001)
Hipke, C.A., Icking, C., Klein, R., Langetepe, E.: How to find a point on a line within a fixed distance. Disc. App. Math. 93(1), 67–73 (1999)
Hoggatt, V., Long, C.: Divisibility properties of generalized fibonacci polynomials. Fibonacci Quart. 12(2), 113–120 (1974)
Koutsoupias, E., Papadimitriou, C.H., Yannakakis, M.: Searching a fixed graph. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 280–289. Springer, Heidelberg (1996)
López-Ortiz, A., Schuierer, S.: The ultimate strategy to search on m rays? Theor. Comp. Sci. 261(2), 267–295 (2001)
De Marco, G., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. Theor. Comp. Sci. 355(3), 315–326 (2006)
Preparata, F.P., Shamos, M.I.: Computational Geometry - An Introduction. Springer (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bose, P., De Carufel, JL., Durocher, S. (2013). Revisiting the Problem of Searching on a Line. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)