||Johns Hopkins University
||Visualization of the Triangle Algorithm
From the REU Website: Dr. Bahman Kalantari is a leading researcher with the Department of Computer Science who was instrumental in developing the field of polynomiography. Polynomiography is a mathematically-inspired computer medium based on algorithmic visualizations of one of the most basic and fundamental tasks in science and mathematics: solving a polynomial equation. Polynomiography serves as a powerful medium for creativity, discovery, and learning, with numerous applications in education, math, science, art and design. Dr. Kalantari will work with a qualified REU student to identify a new problem from polynomiography that will be of interest to both the student and the mentor. In particular, some specific problems will be described from computational geometry, numerical analysis, discrete math, education, algorithmic mathematical art, fine art, and games.
And: The Triangle Algorithm is a newly developed algorithm for testing if the convex hull of a finite set of points contains a distinguished point. It has potential applications in computational geometry, linear programming, convex programming and combinatorial optimization. It also gives rise to new iterative methods for solving a linear system of equations. The goal of this research is to explore some of these possibilities both from the computational points of view as well as theoretical ones.
My project is inspired by Dr. Kalantari's work in polynomiography. I will be working on the visualization of the Triangle Algorithm in R2 using Matlab. There will be applications to (1) learning about the behavior of the algorithm, (2) education - helping younger students to learn about the algorithm and advanced topics such as the convex hull, and (3) algorithmic artwork, much like polynomiography, but using the Triangle Algorithm to develop the images.
Initially, I had also hoped to use polynomiographs to create an animation for visualizing music, but due to time constraints and other difficulties this project with put on hold for now. I wanted to focus on the Triangle Algorithm during my time here at Rutgers.
- Week 1:
- This week was a flurry of activity, from moving into the dorms and meeting all of the other researchers to speaking with faculty mentors and learning more about our research projects. Early in the week, we attended a two-day long workshop lecture with Dr. Emden Gansner, who discussed graph visualization. The talk was illuminating; I hadn't realized how much preparation and mathematics were involved in creating informative, clean diagrams. Learning about that topic helped to nudge me into a new direction for my project as well. Dr. Kalantari and I discussed many different applications for polynomiography, all of which had their merits and challenges. After initial research, reading papers and selections from Dr. Kalantari's book, hearing about the graph visualization, experimenting with the polynomiography software, and exploring on my own, I tentatively decided on the visualization of data using polynomiography, particularly the visualization of music. I have been looking for an application to combine my interests in mathematics and music for some time, and this project has the potential to be very interesting and, ultimately, useful for many people. Music cognition (particularly for people with hearing impediments) is an up and coming field right now. Using mathematics to express a melody (or an entire piece) as a polynomiograph or polynomiograph animation could be a visual aid for such people and way to experience music for others. In addition, music is a complex medium. If enough mathematics can capture some of the aspects of music, moving on to other data (graphs, etc.) would be easier to work with. Dr. Kalantari is supporting my project - and if, after more research, the project becomes too ambitious or not vigorous enough, he said I can always study other aspects of polynomiography and its applications. For now, I am excited to learn more and to continue researching in this area!
- Check out my first presentation (link below) for some examples of music visualization.
- Or, check out these fascinating links:
- Week 2:
- This week, there were several interesting seminars. We learned about Discrepancy Theory with Dr. Raghu Meka, Ramsey Theory with graduate student Kellen Myers, and the basics of html and LaTeX with our REU's graduate coordinator, Glen Wilson. The mathematics talks were interesting, especially the Ramsey Theory discussion. Learning about html was also useful since I'm new to web programming. There was also a Bridge Workshop, where we worked on problems in groups. It was good to flex those problem set focused brain muscles again! In terms of research, I spent a great deal of time investigating other forms of music visualization, especially on creativeapplications.net. Several were compelling, and I found a sound package I that could be potentially used if I made a web based program. However, the more I dug, the more it seemed that polynomiography might not be the best form for this particular project, especially since I'm having trouble with the animation aspects of the software. (The static images were fine - working with the software has been enjoyable, and I've created several polynomiographs that I'm happy with!). Since the visualization project might become too subjective to my artistic tastes, I am expanding my research to more objective mathematics topics. On Dr. Kalantari's recommendation, I read (and am still reading!) many academic papers on both his triangle algorithm and visualizing matrices with polynomiography. I've started coding a visualization program for the triangle algorithm in R2 in Matlab. I think a better goal would be to work on this program and to work on creating a short music visualization demo once the problems with the animation aspects of the software are resolved.
- Week 3:
- We attended two excellent seminars this week. The first was on Tuesday with Dr. Beheshti. She was a dynamic speaker and discussed her interdisciplinary work in Soliton Theory. On Thursday, Dr. Fiorini spoke about forensic mathematics and his past work as a consultant during investigations. As an avid Numb3rs fan, I really enjoyed his talk. In terms of research, I continued reading about the Triangle Algorithm and finished the code for the visualization in Matlab. For now, my code takes in a matrix. The first column holds the x values of the points, and the second column holds the right. The algorithm scales the image area and plots the points. It then iterates through the drawing area, running the triangle algorithm on each point. The color illustrates the number of iterations a particular point can "last" before a witness is found that proves it is not in the convex hull. Right now, the points start out as all black (0). They are brightened (adding .005 each iteration) as more iterations occur. So, in the end, the convex hull is shown in white on a black background, with a gradient along the edges. I'm happy with the images that are being created, and I'm interested to try to code a similar program for R3, perhaps as a projection into R2 or as a 3-D image. (The animation software for polynomiography is still not working, so I have put that on hold for now.)
- Week 4:
- This week, I worked on expanding the visualization of the Triangle Algorithm to colored images in Matlab, not just black and white. The code is working well, especially for symmetric shapes, and the images are interesting. The best color scheme so far is a monochromatic gradient, fading from white to that color. I also added in code to make the vertices of the convex hull stand out. Interestingly enough, when a series of points are the input, my code provides an image for the convex hull, not necessarily the endpoints inputted. The extra points do not make a difference in the images (at least in this algorithm). I experimented with different series of points to see the images that could be created. We also enjoyed Culture Day this week - it was a lot of fun!
- Week 5:
- After meeting with my mentor, I started working on other ways to visualize the Triangle Algorithm. I made another program, this one counting the exact number of iterations it took to have p_prime within an epsilon distance of p. Each point in the screen is a p, and p_prime always starts as the centroid of the convex hull. For this program, I added in many different colors to make the iteration layers stand out. It helps a lot to see what the algorithm is doing. Also, it appears that my first method of visualization is the dual to the way Dr. Kalantari's student proceeded last year. I have started to code up his primal method to contrast the two methods. The images are becoming more interesting and are corresponding to some diagrams in one of Dr. Kalantari's papers! I started working on the polynomiography animation as well, now that the software is working on my laptop. It keeps crashing, though, so I'll have to use the work machines more next week. The Fourth of July was this week, and Dr. Fiorini was nice enough to have us all over for a BBQ! We all had a great time!
- Week 6:
- This week, I continued working on coding the primal algorithm (p always in the centroid of the convex hull, p' changing throughout the image space). The images that I'm creating are interesting (particularly with the color mapping I have now). However, they don't look quite like I thought they would. I just need to spend more time working on the code, and I'm sure that the images will work out. We had some interesting seminar speakers this week as well and took a field trip to the AT&T research center. We listened to many speakers discuss their work, including one man who helped the AT&T team win the million dollar Netflix prize!
- Week 7:
- My computer completely crashed over the weekend. Of course, I didn't have my summer work backed up. It was a minor setback since I had most of the code memorized from working on it so much, but it was still a shame to lose all of that work. I caught up mostly to where I was and changed some parts of the algorithm visualization to account for the epsilon tolerance. Then, I worked on quickly generating images that I'd lost to use for the presentations on Friday. Luckily, I was able to get everything done, and the presentations went well. It was interesting to hear about everyone's projects! Unfortunately, I didn't get to work on the polynomiography animation. I am hoping to try it another time though, on my own. The lesson learned: always, ALWAYS back up your work!
- Week 8:
- It's hard to believe that the REU is over already. This week was very busy. I worked on the final report to be handed in to document the time here doing research and should have it done by the end of this weekend. I met with my faculty mentor, Dr. Kalantari, for the last time. We discussed future research plans and the possibility of trying to publish an article in a math/art journal in the upcoming months. I am going to keep working on the triangle algorithm visualization for the rest of the summer - maybe the results could be published. Dr. Kalantari also took Thomas, Tim, and me out for dinner for the end of the program. Thank you Rutgers, DIMACS, all the faculty involved, and the other students for making this research experience a great one!