Convex Hull Algorithms |
||||
|
|
Work in Progress06.AUG.01 All four algorithms are now complete. Test results have obtained for all four algorithms. You can find them by clicking the Results button on the left. Analysis and final review for optimizing the code is now under way. 15.JUL.01 Tweaks for handling special cases in both Jarvis March and Graham Scan were neccessary. Now that they are complete their results have been posted. Professor Ledin's Extreme algorithm is partly implemented. Issues involving running in greater than linear space are being considered. 03.JUN.01 The Jarvis March and Graham Scan algorithms are now complete and results will be posted soon. Both the algorithms and the structure used for holding and manipulating the points were reworked for efficiency. Also, our CREW project report was submitted indicating our commitment to finish the Jarvis March and Graham Scan algorithms along with Professor Ledin’s algorithm, which is now under review. We hope to have enough results to begin analysis by the end of the month. 25.APR.01 Met with Professor Watts to review heapsort algorithm and discuss ways to modify it for our specific algorithms. We want to check for colinearity and do other computations at the same time as the sorting occurs. Dr. Watts is a professor for the Computer Science department at SSU. Dr. Tia Watts Homepage. 13.MAR.01 Both students are working on coding Jarvis March and Graham Scan from scratch. Additional investigation of other algorithms has produced one or two with similar approaches to our algorithm. Discussion about whether to implement one or both of these algotihms is still on going. 04.FEB.01 Fixed a mathmatical computation in Grahams Scan and worked on implementing a heapsort to complete the algorithm. 15.JAN.01 After a too short winter break returned to the Jarvis March and Grahams Scan coding. Working to find the best way to arrange the structures holding the points and keep them sorted has been tedious. Both students are reviewing the overall approach to make sure that the algorithms are true to their original understanding of them. 1.DEC.00 Met with a SSU math professor, Dr. Elaine McDonald, to discuss the best way to sort by polar angle and to determine whether a "right" or "left" turn had been made to connect three points. Dr. Elaine McDonald's Homepage. 27.NOV.00 Met to work on Graham's Scan and Jarvis' March code. We are in the process of converting existing Graham's Scan code into C++. Jarvis' March is being written from scratch. 4.NOV.00 Setup a general main to run the algorithms and analyze how long they took for various points. Results for the extreme edges algorithm (and eventually other algorithms) can be found here. 10.OCT.00 Students have been working on implementing and understanding either grahams scan or extreme edges algorithm. An implementation of grahams scan was successfully run with the addition of a universal read in and print points created by Traci. Ashley has been translating pseudo code for the extreme edges algorithm into code that also utilizes Traci's read and print points functions. 25.SEPT.00 Added additional links to the links page. 20.SEPT.00 Received a copy of Computational Geometry in C by Joseph O'Rourke. Read through and discussed his description of the Grahams Scan and implementation. 13.SEPT.00 Familiarized ourselves with the Clarkson algorithm. Ran the code and stepped through it to understand what was happening with each line. 6.SEPT.00 Jarvis March and extreme edges algorithms were presented by group members and discussed. 30.AUG.00 Reviewed basic geometric calculations needed to compute the convex hull; such as locating where a point lies in relation to a line and comparing angles to determine where points lie in relation to each other. 17.AUG.00 Updated student schedules and links. 9.AUG.00 Met to review proposal and set goals to accomplish first stage of research. Reviewed website information regarding textbooks on the subject, and students selected algorithm to present to group and first school year meeting. 15.JUL.00 Received notice that our proposal for the Collaborative Research Environment for Women in Undergraduate Computer Science and Engineering was funded. 14.MAY.00 Submitted research proposal and updated website. 05.MAY.00 Currently preparing research proposal. This includes our problem definition which can be found through the research link. Our Fall schedule and bio page links are also available through the links at left.
|