Link to www.uvic.ca

CSC 526: Computational Geometry
Term Summer 2011
Course Website http://www.csc.uvic.ca/courses/csc526
Instructor Sue Whitesides
Email: chair at csc.uvic.ca
Office: ECS 504
Phone Number: (250) 472-5704
Office Hours: TBA
Lecture Schedule 
(A01)   MR   11:30 a.m. - 1:00 p.m.     ECS 130
Course Overview Computational geometry abounds with beautiful problems and solutions that arise in many application domains, including computer graphics, geographic information systems, manufacturing technology, path planning for robots, and graph drawing.
Topics This is an introductory course on low-dimensional computational geometry. We will study algorithmic concepts and data structure techniques for
  • convex hulls
  • triangulations
  • linear programming
  • voronoi diagrams
  • range queries
  • motion planning
Course Objectives And Learning Outcomes Students will gain an understanding of fundamental geometric concepts and problems, as well as algorithmic approaches to solving these problems and an awareness of how these concepts and problems arise in applications. Students will gain experience with formal definitions and proofs, exercising geometric imagination and creativity, modeling problems, and designing algorithmic solutions for them. In addition, students may gain some appreciation for the limitations and challenges of applying theory to concrete problems.
Textbooks
Required: Computational Geometry: Algorithms and Applications
3rd Edition, 2008
Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld, Mark Overmars
Springer-Verlag, ISBN: 978-3-540-77973-5
Other Materials Additional references will be mentioned during class. While it is assumed that everyone has access to the required text, note that a similar version is available on line, but the page numbering and some content is slightly different.
Assignments In this course there will be approximately 4-5 assignments, equally weighted, for a total of 20%. Typically, 1-2 weeks will be given for each assignment.
Quizzes There are no quizzes in this course. There will be, however, a variety of ungraded in-class activities.
Project(s) There will a paper/project worth 10%.
Each student will also keep a geometry logbook, worth 10%. The logbook will record ideas, references, plans for the paper/project, and also feedback and reflections on the presentations of the graduate students.
Exams There will be a midterm and a final exam. The midterm exam is worth 20% and takes place on or about Monday, June 13. The final exam is worth 40% and will be scheduled by the University.

Because the final exam is scheduled by the university, you are strongly advised not to make final plans for travel or employment during the exam period since special arrangements will not be made for examinations that may conflict with such plans.
Term Schedule This preliminary schedule may change.

Assignment/Tests/Other Weight Assigned Date Due Date
Assignment 1 5% Week 1 Week 2
Assignment 2 5% Week 3 Week 4
Logbook (with initial topic proposal) 4% Week 1 Week 5
MIDTERM (week 7) 20% June 13 June 13
Assignment 3 5% Week 8 Week 9
Assignment 4 5% Week 9 Week 10
Logbook (with final topic choice) 4% Week 1 Week 11
Paper 10% Week 1 Week 12
Logbook (with presentation reviews) 2% Week 12 Week 13
Final Exam 40% N/A to be scheduled by the University
Grading
Coursework Weight (out of 100%)
Assignments 20%
Midterm Exam 20%
Paper or Project, and its Presentation 10%
Presentation Reviews and Logbook 10%
Final Exam 40%

Grades Description
A+ Exceptional work. Technically flawless and original work demonstrating insight, understanding and independent application or extension of course expectations; often publishable.
A Outstanding work. Demonstrates a very high level of integration of material demonstrating insight, understanding and independent application or extension of course expectations.
A- Excellent work. Represents a high level of integration, comprehensiveness and complexity, as well as a mastery level of relevant techniques/concepts..
B+ Very good work. Represents a satisfactory level of integration, comprehensiveness and complexity; demonstrates a sound level of analysis with no major weakness.
B Acceptable work that fulfills the expectations of the course. Represents a satisfactory level of integration of key concepts/procedures. However, comprehensiveness or technical skills may be lacking.
B-, C+, C, D Unacceptable work revealing some deficiencies in knowledge, understanding or techniques. Represents an unacceptable level of integration, comprehensiveness and complexity. Mastery of some relevant techniques or concepts lacking.
F Failing grade. Unsatisfactory performance. Wrote final examination and competed course requirements.


Scores are transformed into letter grades as follows: When all the coursework marks have been determined, the instructor will use the description in the table above to determine threshold marks for A+ and F. The interval between the thresholds will be divided into 8 equal subintervals, with possible adjustment up or down by 3 marks to handle clusters. The subintervals thus determined correspond to the grades in the range A through D.


Posting Of Grades Term marks, provisional final grades and final grades will be posted on the course's conneX site by abbreviated student number. NO NAME WILL APPEAR. These postings are for your information and for your validation of the data entry. If you do not wish your term marks and grades to be viewable by others in the class in this manner, please notify the course instructor by e-mail no later than Friday, May 13, 2011 .
Csc Student Groups The Computer Science Course Union (http://cscu.csc.uvic.ca/mediawiki/index.php/) serves all students who are either in a computer science program or taking a class in computer science. Please sign yourself up on their mailing list if you would like to be informed about their social events and services.

Women in Engineering and Computer Science (http://wecs.uvic.ca/) - The purpose of the WECS is to encourage more women and girls to consider Computer Science or Engineering as a career and to support them in their decision once they arrive at UVic.

The Engineering Students' Society (ESS) serves all students registered in an Engineering degree program, including Software Engineering (BSEng). For information on ESS activities, events and services navigate to http://www.engr.uvic.ca/~ess .
Course Policies And Guidelines Late Assignments: Late assignments will normally not be accepted unless prior arrangements have been made with the instructor well in advance of the assignment due date.
Coursework Mark Appeals: All marks must be appealed within 10 days of the mark being posted.
Attendance: Students are expected to attend all class meetings. It is entirely the students' responsibility to recover any information or announcements presented in lectures from which they were absent.
Electronic devices in labs and lectures: No unauthorized audio or video recording of lectures is permitted.
Electronic devices in midterms and exams: Calculators are only permitted for examinations and tests if explicitly authorized and the type of calculator permitted may be restricted. No other electronic devices (e.g. cell phones, pagers, PDA, etc.) may be used during examinations or tests unless explicitly authorized.
Plagiarism: Submitted work may be checked using plagiarism detection software. Cheating, plagiarism and other forms of academic fraud are taken very seriously by both the University and the Department. You should consult http://web.uvic.ca/calendar/FACS/UnIn/UARe/PoAcI.html for the UVic policy on academic integrity. Note that the university policy includes the statement that "A largely or fully plagiarized assignment should result in a grade of F for the course".

The Faculty of Engineering Standards for Professional Behaviour are at http://www.uvic.ca/shared/shared%5fengineering/docs/professional-behaviour.pdf

The department guidelines concerning fraud are at http://www.csc.uvic.ca/courseinfo/policies/fraud.html

Department Policies: A list of department policies regarding all courses may be found at http://www.csc.uvic.ca/courseinfo/policies/index.html

This course aims to provide equal opportunities and access for all students to enjoy the benefits and privileges of the class and its curriculum and to meet the syllabus requirements. Reasonable and appropriate accommodation will be made available to students with documented disabilities (physical, mental, learning) in order to give them the opportunity to successfully meet the essential requirements of the course. The accommodation will not alter academic standards or learning outcomes, although the student may be allowed to demonstrate knowledge and skills in a different way. It is not necessary for you to reveal your disability and/or confidential medical information to the course instructor. If you believe that you may require accommodation, the course instructor can provide you with information about confidential resources on campus that can assist you in arranging for appropriate accommodation. Alternatively, you may want to contact the Resource Centre for Students with a Disability located in the Campus Services Building.

The University of Victoria is committed to promoting, providing, and protecting a positive, and supportive and safe learning and working environment for all its members.