Abstract
Shoreline search is a natural and well-studied generalisation of the classical cow-path problem: k initially co-located unit speed agents are searching for a line (called shoreline) in 2 dimensional Euclidean space. The shoreline is at (a possibly unknown) distance \(\delta \) from the starting point \(O\) of the agents. The goal is to minimize the competitive ratio \(\frac{T_{\delta }}{\delta }\), where \(T_{\delta }\) is the worst case (over all possible locations of the shoreline at distance \(\delta \)) time until the shoreline is found.
Upper bounds conjectured to be optimal have been established for all \(k\ge 1\) [4], however lower bounds have been severely lacking. Recent paper [1] showed an improved lower bound for \(k=2\) and gave the first non-trivial lower bounds for \(k\ge 3\). While for \(k\ge 4\) the lower bounds match the best known upper bounds, that is not the case for \(k<4\).
In this paper we improve the lower bound for \(k=2\) from 3 to \((1+\sqrt{3}+\pi /6) \approx 3.2556\), and for \(k=3\) from \(\sqrt{3}\) to 2. These lower bounds apply for known \(\delta \), matching the corresponding upper bounds. In fact, for \(k=3\) our lower bound matches the upper bound for unknown \(\delta \) as well.
We achieve these results by employing a novel simple virtual colouring technique, allowing us to transform the problem of covering the (uncountably many) points of the circle of radius \(\delta \) (whose tangents represent all possible shorelines at distance \(\delta \)) to a combinatorially much simpler problem of finding the shortest path from the centre to three specific tangents of this circle.
Research supported by VEGA 1/0601/20.
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
Similar content being viewed by others
References
Acharjee, S., Georgiou, K., Kundu, S., Srinivasan, A.: Lower bounds for shoreline searching with 2 or more robots. In: OPODIS (2019)
Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R., Subrahmanian, V.: Search Theory: A Game Theoretic Perspective. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-6825-7
Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous, vol. 55. Springer, Boston (2006). https://doi.org/10.1007/b100809
Baeza-Yates, R., Schott, R.: Parallel searching in the plane. Comput. Geom. 5(3), 143–154 (1995)
Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching with uncertainty extended abstract. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 176–189. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-19487-8_20
Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching with uncertainty (technical report 239). Indiana University, Computer Science Department (1988)
Bellman, R.: A minimization problem. Bull. AMS 62(3), 270 (1956)
Benkoski, S.J., Monticino, M.G., Weisinger, J.R.: A survey of the search theory literature. Naval Res. Logist. (NRL) 38(4), 469–494 (1991)
Czyzowicz, J., Georgiou, K., Kranakis, E.: Group search and evacuation. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities. LNCS, vol. 11340, pp. 335–370. Springer, Cham (2019)
Dobbie, J.M.: A survey of search theory. Oper. Res. 16(3), 525–537 (1968)
Gal, S.: Search games. In: Wiley Encyclopedia of Operations Research and Management Science (2010)
Gluss, B.: An alternative solution to the “lost at sea” problem. Naval Res. Logist. Q. 8(1), 117–122 (1961)
Gluss, B.: The minimax path in a search for a circle in a plane. Naval Res. Logist. Q. 8(4), 357–360 (1961)
Isbell, J.R.: An optimal search pattern. Naval Res. Logist. Q. 4(4), 357–359 (1957)
Jeż, A., Łopuszański, J.: On the two-dimensional cow search problem. Inf. Proc. Lett. 109(11), 543–547 (2009)
Langetepe, E.: On the optimality of spiral search, pp. 1–12, January 2010
Langetepe, E.: Searching for an axis-parallel shoreline. Theor. Comput. Sci. 447, 85–99 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Dobrev, S., Královič, R., Pardubská, D. (2020). Improved Lower Bounds for Shoreline Search. In: Richa, A., Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2020. Lecture Notes in Computer Science(), vol 12156. Springer, Cham. https://doi.org/10.1007/978-3-030-54921-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-54921-3_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-54920-6
Online ISBN: 978-3-030-54921-3
eBook Packages: Computer ScienceComputer Science (R0)