General Information

Student: Colin Jarvis
Office: CORE 434
School: Macalester College
E-mail: cjarvis (at) macalester (dot) edu
Project: Applications and Visualization of the Triangle Algorithm

Project Description

Given n m-dimensional points and a target point p, we would like to know whether a target point p is in the convex hull of the set of n points. Based on a simple yet powerful theorem that makes use of the duality of this convex hull problem, Dr. Kalantari's Triangle Algorithm is an iterative method that approximates the target point p.


Weekly Log

Week 1:
I arrived at Rutgers and met with my mentor Dr. Kalantari for the first time to discuss possible directions for my project. I spent most of the week reading the relevant background literature and carefully considered which of several possible projects relating to Dr. Kalantari's work I would like to pursue.
Week 2:
This week I explored Dr. Kalantari's polynomiography software and acquainted myself therein. After further discussion of the project, I have settled on Dr. Kalantari's Triangle Algorithm as a method of investigation and exploration.
Week 3:
I coded Dr. Kalantari's triangle algorithm to visualize the convergence iterations for the trivial case of a square convex hull formed by four points in a plane.
Week 4:
This week I added some features to my triangle algorithm visualization program and we found that by including the midpoints between the vertices as pivots, we can significantly cut the worst case iteration time. I was fortunate enough to attend the International Symposium on Voronoi Diagrams (ISVD 2012) held on Wednesday, Thursday, and Friday at DIMACS. It was a great learning experience to be a participant in an international professional mathematical conference.
Week 5:
I discussed with my mentor the possible applications of the Triangle Algorithm and potential methods to speed up the rate of convergence.
Week 6:
I coded the Triangle Algorithm for n points in m dimensions with plans to make the program more robust with additional features.
Week 7:
More coding this week with a focus on applications of the triangle algorithm. The REU students capped the week by giving our final presentations of our summer's research (see below).
Week 8:
The final week was used to tie up all the loose ends from the summer and write a final report. My mentor and I mapped out the areas of my project that present the opportunity for further investigation.


Additional Information