DLS • Joe Mitchell • Fun with Geometric Optimization: Visitation, Visibility, and Variations

Joe Mitchell
​Department of Applied Mathematics and Statistics
State University of New York at Stony Brook 

Optimization problems that involve geometric data abound in everyday life. Classic examples include the traveling salesperson problem (TSP), the "art gallery" visibility coverage problem, and searching in a geometric domain. Many of these problems are NP-hard but have good approximation algorithms that exploit geometric structure. A particular challenge is to address optimization problems when there is uncertainty in the input data.

We survey a small subset of such problems, examine some models of geometric optimization in the face of uncertainty, and describe some approximation algorithms for their solution. One example problem we discuss is the "adversarial TSP" problem in which the goal is to determine the order in which to visit a set of "uncertainty regions," each of which has a specific point site that must be visited, but an adversary gets to pick the (worst possible) location of the site within each uncertainty region, after we have announced the order in which we will visit the sites/regions.

Bio: Joe Mitchell is a leader in computational geometry, which studies the design, analysis, and implementation of efficient algorithms to solve geometric problems. His particular interest is applications to problems in computer graphics, visualization, robotics, manufacturing, geographic information systems, and computer vision.  A major current application is helping air traffic controllers route airplanes around bad weather.

Did you miss Joe Mitchell's lecture or would you like to hear it again? If so, just start the video below.