M-R 2-3:20pm
Location: MRC 334 (conf. room)
Instructor: Ibrahim Volkan Isler
Tentative schedule
|
Summary:
Robots and sensor-networks are inherently tied to the
physical world. Consequently, most optimization problems which arise in
these fields can be solved using geometric techniques. This course will
cover a variety of techniques that should be useful for robotics and
sensor-networks researchers. The list of topics include:
Part I: Basic
Geometric Optimization Problems
- Point Location
- Convex Hulls
- Linear Programming
- Proximity queries (Voronoi Diagrams, Triangulations, ...)
- Geometric Searching
- Sampling and shape approximation
Part
II: NP-hard Geometric
Optimization Problems
- Covering and partitioning
- Network design: steiner tree problem and variants
- Routing: Traveling Salesperson Problem and Variations
Part III: Selected Topics
- an assortment of robotics and sensor-networks papers
that
utilize geometric optimization techniques
|
Suggested texts:
- Computational Geometry: Algorithms and Applications by de
Berg, van Kreveld, Overmars and Schwarzopf
- Approximation Algorithms by Vazirani
|
Prerequisites:
CSCI-4020 Computer Algorithms, or equivalent.
|
Grading:
- Project: 60%. The project consists of literature &
background review + lecture and solution of a novel/open problem
and a presentation. For the first part, you should prepare a webpage
with pointers and references to relevant papers, slides etc. For the
second part, a term report is required. We will discuss the project in
detail in the first class.
- Take-home Final: 30%
- Participation: 10%
|