Course description Description Computational geometry is the design and analysis of algorithms for solving geometric problems The field emphasizes solution of geometrical problems from a computational point of view Geometry is a very classical subject which has been by studied by Euclid Descartes Gauss Hilbert Klein and many other mathematical genius They developed mathematical formalism for representations of geometric entities effects of transformation in space and geometric reasoning But they were not concerned with the efficiency of geometric computation because computers and the concep of algorithm complexities were non existent Solid Modeling Design and analysis of systems for representing 3dimensional objects and computational geometry ideas are very useful in this field Computer Graphics Methods for modeling and rendering scenes Visualization of the objects of the scene on a computer screen is implicit in the definition Visualization Methods of rendering an image on computer screen using pixel or voxel data for objects corresponding to surface and volume rendering Computer Vision Virtual Reality Robotics use computational geometry concepts Computational geometry emerged as a unified discipline in 1978 with the appearance of Shamos Ph D dissertation Since then research interest has been high Many fascinating and beautiful results have been produced Application areas 1 Computer graphics 6 Computer generated forces 2 Solid modeling 7 Computer aided manufacturing 3 Terrain representation 8 Robotics 4 Virtual reality 9 Computer vision 5 Simulation 10 Image Compression 11 VLSI design Goals 1 Familiarize the student with the fundamental algorithm techniques for designing efficient algorithms dealing with collections of geometric objects 2 Show by example how the algorithms are useful in the various application domains Course particulars Term Fall 2003 Meets Monday and Wednesday 16 30 17 455 Room ENG II 302 Prerequisite COT 5404 Design and Analysis of Algorithms or instructor s permission Instructor Amar Mukherjee Email amar cs ucf edu Phone 407 823 2763 M W15 30 16 30 Room CSB208 Office Hours Dr Mikel Petty a former student of this course prepared many of the slides presented here Classes Begin August 25 Late Registration and Add Drop ends at 5 00 p m on the last day August 25 29 Last Day for Full Refund ends at 5 00 p m on the last day August 29 Withdrawal Deadline ends at 5 00 p m on the last day October 17 Classes end December 5 Final Exam December 8 4to 6 50pm Fall Holidays and Events Labor Day September 1 Homecoming WeekOctober 20 25 Veteran s Day November 11 Thanksgiving November 27 30 Examples Convex polygon intersection Voronoi diagram Miscellaneous notes Lectures will start on time 15 minute cutoff Office hours Hour before class Phone calls or Email welcome No extensions on due dates turn work in as is on due date Partial credit given for partial results Electronic submission of assignments OK but instructor not responsible for Email failures Attendance is compulsory unless the student has medical reasons or emergency circumstances Missing class without justification will result in grade penalty Errors in texts or lecture transparencies worth bonus point each to first person who finds them Course texts Computational Geometry Algorithms and Applications M de Berg M van Krevold M Overmars and O Schwarzkopf Springer Verlag 1997 BKOS Excellent exposition of most of the important topics lack of formal development of the subject matter in a natural progresion A copy available at the library reserve desk Computational Geometry An Introduction Franco P Preparata and Michael Ian Shamos Springer Verlag 1988 PS Based on Shamos dissertation original computational geometry text Numerous small errors and typos exposition sometimes difficult to follow some recent results missing Still unmatched in terms of comprehensive coverage of field Out of print one copy put in library reserve Computational Geometry in C Joseph O Rourke Cambridge University Press 1995 Much more recent than Preparata and Shamos Clearer easier to understand Coverage not as complete focused on C A copy available at the library reseve desk JR Computational Geometry and Computer Graphics in C Michael J Laszlo Prentice Hall 1996 Libray copy Considerable background material data structures complexity Very good explanations of covered algorithms if you know C ML Course topics Subject to Change Based on Preparata Shamos book We will cover all the topics here not necessarily in the same sequence We will try to follow the sequence in the text BKOS remembering that the material from PS are essential to this course Most of the slides here were prepared before BKOS was published so you may have to adjust back and forth with notations as we proceed There will be additional reading assignments from other texts copies available at the library reserve Preliminaries Ch 1 Definitions Coordinate systems Vector algebra Line equations Data structures Model of computation Complexity notation Geometric searching Ch 2 Point location Range searching Convex hulls Ch 3 Graham s scan Jarvis s march Divide and conquer Dynamic hull Proximity Ch 5 Closest pairs Voronoi diagrams Triangulation Ch 6 Intersections Ch 7 Segment intersection Rectangle intersection Convex polygon intersection Convex polyhedra intersection Course grading Overview Subject to Change 1 Homework 2 Midterm examination s 3 Final examination 4 Course project 35 20 25 20 Homework Weekly biweekly assignments 2 4 problems approximately 1 6 hours total per week Problems drawn from text exercises and other sources Each homework assignment will be assigned 50 100 points Discussion and presentation of homework problems by students encouraged Homework assignments will have different weights Weighted sum of points will contribute to total homework score Total homework points earned divided by total homework points possible to get portion of overall grade 35 Reading assignments will be from all three texts You will be asked questions from text material as well as reading assignments All answers must be prepared by the students independently they are welcome to discuss the principles and methods to solve a problem but specific answers to homework problems should not be discussed Penalty for cheating or copying will be severe Midterm and final examinations Problems similar to homework problems in type and topic Doing homework will be best preparation Course grading Course project One of