||cjarvis (at) macalester (dot) edu
||Applications and Visualization of the Triangle Algorithm
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.
- 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
- 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.