|
HU Credits:
3
Degree/Cycle:
2nd degree (Master)
Responsible Department:
computer sciences
Semester:
1st Semester
Teaching Languages:
Hebrew
Campus:
E. Safra
Course/Module Coordinator:
Leo Joskowicz
Coordinator Office Hours:
By appointment
Teaching Staff:
Prof Leo Joskowicz
Course/Module description:
Computational Geometry is the algorithmic study of geometrical entities, their properties, and the operations on them. Examples include the intersection of line segments, the tessellation of a set of points, and the construction of nearest neighbor graphs. The
algorithms and their properties form the basis of numerous fields, such as Computer
Graphics, Computer Vision, Computer-Aided Design, and Robotics.
In this course, we will study the basic geometric constructs of Computational Geometry,
including 2D and 3D convex hulls, planar triangulations, Voronoi diagrams, and
Arrangements in 2D and 3D. We will learn about deterministic and randomized
algorithms and their data structures for computing them efficiently and for computing
fundamental geometric problems including polygon triangulation, point location, range
queries, and applications in motion planning. The course will be taught so as to balance
between theoretical and applied issues.
Course/Module aims:
The aim of the course is to familiarize the students with the central concepts of Computational Geometry.
The main topics are:
1. Introduction - geometric primitives
2. Convex Hulls in 2D and 3D
3. Sweep line algorithms - line segment intersection
4. Boolean operations of polygons
5. Polygon decompositions - Triangulations
6. Voronoi Diagrams and Delaunay triangulations
7. Orthogonal Range Searching - KD trees and Range trees
8. Point locations queries
9. Linear programming - geometric interpretation
10. Duality of points and lines
11. Arrangements of lines
12. Motion planning and visibility graphs
Learning outcomes - On successful completion of this module, students should be able to:
At the end of the course, the students will be able to design, analyze, and develop algorithms and methods for solving geometric problems efficiently. The students will be able to assess theoretical and practical problems that involve geometry and will devise and adapt efficient methods to solve them, or prove that they cannot be solved efficiently.
Attendance requirements(%):
none
Teaching arrangement and method of instruction:
Frontal lectures and exercise lectures. Five by-weekly homeworks. No programming required.
Course/Module Content:
The detailed content of the course is:
1.Geometry basics, 2D convex hulls
• Types of polygons: convex, star, monotone, simple, holes
• Convex hull properties
• Euler’s formula for planar subdivisions
• Data structure for planar subdivision
2. Line and segment intersection
• Sweep line algorithm
• Boolean polygon operations: intersection, union, difference
• Convex polygon intersection; polygon tangents
3. Polygon triangulation
• Triangulation theory – dual graph, diagonals
• Monotone polygon triangulation
• Simple polygon partition into monotone polygons
• Trapezoidal partition
4. Orthogonal range searching
• Grids, quad trees
• Range trees (2D and higher)
• Kd trees (2D and higher)
5. Quadtrees
• Uniform and non-uniform grids
• Quadtrees properties
• Quadtree construction and query algorithms
6. Point location
• Monotone polygon
• Monotone chains
• Trapezoidal decomposition and complexity
• Triangular decomposition – method and complexity analysis
7. Voronoi diagrams
• Definitions, basic properties
• Incremental construction
• Sweep line algorithm – in detail.
• Divide and conquer, VD variations and extensions
8. Delaunay triangulations
• Basic properties of triangulations
• Illegal edges, flips, Thales theorem
• Delaunay triangulation – duality Voronoi diagram
• Incremental algorithm and complexity
9. Arrangements and duality
• Line arrangements: definition, properties
• Zone theorem in detail
• Incremental algorithm
• Duality transform
• Levels computation
• Applications – relation to convex hull
10. Linear Programming
• Formulation and geometric interpretation
• Incremental algorithm
• Randomized analysis
• Unboundedness test
11. 3D Convex Hull
• Basic properties of 3D CH
• Incremental algorithm
• Divide and conquer algorithm
• Relation between CH, Voronoi Diagram and Triangulation
12. Motion planning and visibility graphs
• Problem definition
• Basic approaches
• Trapezoidal cell decomposition
• Visibility graph
• Configuration spaces
13.Minkowsky sums
14. Advanced topics
Required Reading:
Reference Book: Computational Geometry: Algorithms and Applications, M. de
Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf 3nd Ed, Springer‐Verlag, 2008.
Instructor's lecture and exercise notes in the Moodle CSE web site
Additional Reading Material:
none
Course/Module evaluation:
End of year written/oral examination 70 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 30 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %
Additional information:
none
|
