Point separation
| Linear Programming | |
|---|---|
 | |
| MATH340 | |
| Section: | 921 |
| Instructor: | Tali Pinksky |
| Email: | tali@math.ubc.ca |
| Office: | Math 229a |
| Office Hours: | Wed 1-2 pm or by appointment |
| Class Schedule: | Tue-Thu-Fri 2-4 pm, Wed 2-3 pm |
| Classroom: | Math Annex 1100 |
| Important Course Pages | |
| Resources | |
| Assignments | |
| Discussion | |
| Projects | |
Given a set of points in a plane, what is the best way to separate them into two groups using a line? Using a circle? How about an annulus?
These all can be formed as LP problems, and all have important applications to data analysis.
Try looking at this chapter from a computational geometry course in ETH, and choose your favourite separation problem. Show how this can be written as an LP problem. See also this paper.