Πολυδιάστατες Δομές Δεδομένων και Υπολογιστική Γεωμετρία (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 ? Learning Outcomes
The course?s aim is to introduce students to the basic multidimensional data structures, such as: Interval Tree, Priority Search Tree, Segment Tree, Range-tree, Rectangle-tree (R-tree), Quad-Tree and kd-tree as well as to applications of the above advanced data structures in computational geometry and graphics like: Raster Display 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, 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:
- ?Προχωρημένες Δομές δεδομένων και Computer-Γραφική?, Α. Κ. Τσακαλίδης, Εκδόσεις Πανεπιστημίου Πατρών, 2010.
- ? Υπολογιστική Γεωμετρία ? Αλγόριθμοι και Εφαρμογές», De Berg Mark, Cheong Otfried, Van Krevel Marc, Overmars Mark, Ίδρυμα Τεχνολογίας & Έρευνας ? Πανεπιστημιακές Εκδόσεις Κρήτης, 2011.
- Υπολογιστική Γεωμετρία: Μια Σύγχρονη Προσέγγιση, Γιάννης Ζ. Εμίρης, Εκδόσεις Κλειδάριθμος ΕΠΕ, 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%)
Λιγότερα
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 ? Learning Outcomes
The course?s aim is to introduce students to the basic multidimensional data structures, such as: Interval Tree, Priority Search Tree, Segment Tree, Range-tree, Rectangle-tree (R-tree), Quad-Tree and kd-tree as well as to applications of the above advanced data structures in computational geometry and graphics like: Raster Display 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, Overlapping Polygons Area Computation, Hidden line elimination problem, Line Segment Intersection, Polygon
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 ? Learning Outcomes
The course?s aim is to introduce students to the basic multidimensional data structures, such as: Interval Tree, Priority Search Tree, Segment Tree, Range-tree, Rectangle-tree (R-tree), Quad-Tree and kd-tree as well as to applications of the above advanced data structures in computational geometry and graphics like: Raster Display 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, Overlapping Polygons Area Computation, Hidden line elimination problem, Line Segment Intersection, Polygon
