DLS • Joe Mitchell • Fun with Geometric Optimization: Visitation, Visibility, and VariationsExport this event to calendar

Wednesday, May 23, 2018 3:30 PM EDT

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

photo of Professor Joe MitchellOptimization 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.

Location 
DC - William G. Davis Computer Research Centre
1302
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2024 (96)
    1. April (19)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)