נקודות זכות באוניברסיטה העברית: 3

תואר: מוסמך

היחידה האקדמית שאחראית על הקורס: מדעי המחשב

סמסטר: סמסטר א'

שפת ההוראה: עברית

קמפוס: קרית א"י ספרא

מורה אחראי על הקורס (רכז): Leo Joskowicz

דוא"ל של המורה האחראי על הקורס: josko@cs.huji.ac.il

שעות קבלה של רכז הקורס: By appointment

מורי הקורס:
פרופ לאו יוסקוביץ

תאור כללי של הקורס:
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.

מטרות הקורס:
The course syllabus consists of:

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

תוצרי למידה :
בסיומו של קורס זה, סטודנטים יהיו מסוגלים:
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.

דרישות נוכחות (%):
none

שיטת ההוראה בקורס: Frontal lectures and exercise lectures. Five bi-weekly homeworks, No programming required.

רשימת נושאים / תכנית הלימודים בקורס:
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

חומר חובה לקריאה:
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

חומר לקריאה נוספת:
none

הערכת הקורס - הרכב הציון הסופי :
מבחן מסכם בכתב/בחינה בעל פה 70 %
הרצאה0 %
השתתפות 0 %
הגשת עבודה 0 %
הגשת תרגילים 30 %
הגשת דו"חות 0 %
פרויקט מחקר 0 %
בחנים 0 %
אחר 0 %

מידע נוסף / הערות:
none