- Start Date:
June 21, 2016
- Event Start Time:
2:00 PM
- Event End Time:
3:00 PM
- Organizers:
Lazaros Gallos
- Seminar Series:
REU Seminar
- Presenter(s):
Bahman Kalantari - Rutgers University
- Event Location:
DIMACS Seminar room
- Abstract:
How do you check if a point is inside a triangle? That’s easy, you look! What if you are given a set S with 1,000,000 points in dimension 500 and want to check if a specific point p in this dimension lies in the convex hull of S? Not easy anymore! Let’s call this the convex hull membership problem. Here is a way to check: Step 0: Hire the Spider-Man. Step 1: Place him anywhere in the convex hull of S. Step 2. Look for a point v in S (called pivot) that is farther away from the Spider-Man than from p (the Villain). From here on Spider-Man knows what to do: He will throw his web to v, pull himself toward it until he is closest to the Villain along this direction. He then repeats the process from the new position until sufficiently close to capture him. What if there is no pivot at a specific location? He cannot catch the Villain! This is the Triangle Algorithm and the name of the game is, ``Catch me if you can.’’ In each iteration the action is between the Spider-Man, the Villain and a pivot, regardless of the dimension.
I will describe the significance of the convex hull membership problem, its equivalence to linear programming, the complexity of the Triangle Algorithm as a fully polynomial time approximation scheme, and how it compares with polynomial-time algorithms for LP, or with the simplex method. Next, I will sketch a version of the algorithm to test if the convex hull of two finite sets of points intersect, called the support vector machine, a significant problem in machine learning. The players in the general version of the Triangle Algorithm are Spider-Man and Spider-Woman. And the name of the game is, ``Can Romeo and Juliet unite?” Finally, I will give ideas on how to create artwork from the Triangle Algorithm, even with a few points in the plane, and some computer programming.
