Acharjee, Sumi.pdf (1.37 MB)
Download file

Searching for a Shoreline

Download (1.37 MB)
thesis
posted on 25.05.2022, 17:10 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.


History

Language

English

Degree

Master of Science

Program

Applied Mathematics

Granting Institution

Ryerson University

LAC Thesis Type

Thesis

Thesis Advisor

Konstantinos Georgiou