Πολυδιάστατες Δομές Δεδομένων (PDDYG)

Description:

The course is an introductory course to multi-dimensional data structures and computational geometry, for students that have basic knowledge of simple data structures, algorithms and procedural or object oriented programming (C, C++ programming language).

Aims and  Learning Outcomes

The course's aim is to introduce students to the basic multidimensional data structures, such as: Interval Trees, Priority Search Trees, Segment Trees, Range-trees, Rectangle-trees (R-trees), Quad-Trees and kd-trees as well as to applications of the above advanced data structures in the following areas of Spatial and Spatio-Temporal Databases, Computational Geometry and Graphics: Indexing Mobile Objects, Raster-Display Bresenham's Algorithms  for points, lines and circles, 2-dimensional transformations, window and cutting algorithms, segment-clipping algorithms, Cutting Polygons, View Transformations, Overlapping Polygons Area Computation, Hidden line elimination problem, Line Segment Intersection, Polygon Triangulation, Linear Programming in Geometry, orthogonal range searching, Point Location Algorithms, Voronoi Diagrams, Delaunay Triangulation, Geometrical Data Structures, Convex Hull, Binary space partitions, Visibility graphs.

After having successfully completed the course the student will be able to:

• Understand the basic concepts of multidimensional data structures
• Implement and manage the basic multidimensional data structures
• Understand the basic tools of design and analysis of algorithms for solving problems, especially in computational geometry
• Choose the proper multidimensional data structure for solving the geometric problem at hand.

Syllabus:

Week #1:

Interval Tree and applications

Week #2:

Priority Search Tree and applications

Week #3:

Segment Tree and applications

Week #4:

Range-tree and Fractional Cascading

Week #5:

R-tree, Quad-Tree and kd-tree

Week #6:

Sweep line technique, Overlapping Polygons Area Computation, Hidden line elimination problem

Week #7:

Raster Display Stores for lines and points, the basic incremental algorithm, the algorithm of Bresenham for lines, the algorithm of Bresenham for circles, 2-dimensional transformations, window and cutting algorithms, segment-clipping algorithms, cutting polygons, view transformations

Week #8:

Line Segment Intersection, Polygon Triangulation

Week #9:.

Linear Programming in Geometry

Week #10:.

Orthogonal Range Searching and Point Location Algorithms

Week #11:

Voronoi Diagrams and Delaunay Triangulation

Week #12:

Geometrical Data Structures and Convex Hull Computation

Week #13:

Binary space partitions and Visibility graphs

Bibliography:

1. Προχωρημένες Δομές δεδομένων και Computer-Γραφική?, Α. Κ. Τσακαλίδης, Εκδόσεις Πανεπιστημίου Πατρών, 2010.
2. Υπολογιστική Γεωμετρία ? Αλγόριθμοι και Εφαρμογές», De Berg Mark, Cheong Otfried, Van Krevel Marc, Overmars Mark, Ίδρυμα Τεχνολογίας & Έρευνας ? Πανεπιστημιακές Εκδόσεις Κρήτης, 2011.
3. Υπολογιστική Γεωμετρία: Μια Σύγχρονη Προσέγγιση, Γιάννης Ζ. Εμίρης, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2008.

Educational and learning methods:

• Lectures
• Practice exercises focusing on the application of methodologies and analysis of case studies to smaller groups of students
• Assignment support

Evaluation methods:

• Written final exam (60%) including:

• Judgment and brief development questions
• Problem-solving questions (unknown and relevant to the ones taught) and implementation of a pseudo-code solutions
• Comparative evaluation of theory

• Assignments (40%)

• Presentation (5%)
• Design and development (35%)