Grant: Discovery Grants Program - Individual

We propose to study polygon search problems in computational geometry and robotics. Computational geometry is the study of algorithms to solve problems related to geometry. In many applications of the discipline, visibility problems play a fundamental role. In essence, given a polygon, if the line segment connecting two given points is within the polygon, we say that the two points are mutually visible. Despite its simple definition, there are many intriguing problems related to it. Motion planning in robotics is one of the applications related to visibility problems. Basically, it asks how to plan the movement of robots in a given area such that any intruders inside the area will be detected. Our work studies motion planning for robots at an abstract level. It was coined as the polygon search problem, in which the given area is delineated as a simple polygon and the robots (also called searchers or guards) and intruders are represented as mobile points. Our research centers around three directions of the polygon search problem. (1) Characterization of searchable polygons, in terms of the geometric patterns, under different settings of searchers, such as a 1-searcher, who is equipped with one flashlight; (2) Generation of a search schedule that the searcher(s) can follow to search a polygon, once the polygon is determined to be searchable; (3) On-line search in a polygon with unknown geometric properties, such as its edges and vertices. Our study will improve our understanding of polygon search problems, provide further improvements to the current results, and solve new proposed problems.