Abstracts Mathematics

Searching for a Shoreline

by Sumi Acharjee

Search theory has a long history that dates back to the 50’s. In this work, we focus on the two-dimensional search problem where n unit speed robots starting from the origin move along their own trajectories to find a line. The search algorithm terminates when any of the robots discovers the line for the first time. Our main objective is to minimize the worst case relative time until the first searcher hits the line. In this thesis, we do the competitive analysis of the two-dimensional search problem for n ≥ 2 and restudy the existing upper bounds for n ≥ 2. We improve the best lower bound known [8] for n = 2 robots from 1.5993 to 3. Also, we prove the first lower bound for n = 3 which is √ 3. For n ≥ 4 we prove the lower bound of 1 cos(π/n) which matches the best upper bound known.