Universidad de Jaén

Menú local

Syllabus 2017-18 - 13313001 - Geometric Algorithms (Algoritmos geométricos)

Caption
  • Level 1: Tutorial support sessions, materials and exams in this language
  • Level 2: Tutorial support sessions, materials, exams and seminars in this language
  • Level 3: Tutorial support sessions, materials, exams, seminars and regular lectures in this language
DEGREE: Grado en Ingeniería informática
FACULTY: SCHOOL OF ENGINEERING OF JAÉN
ACADEMIC YEAR: 2017-18
COURSE: Geometric Algorithms
SYLLABUS
1. COURSE BASIC INFORMATION
NAME: Geometric Algorithms
CODE: 13313001 ACADEMIC YEAR: 2017-18
LANGUAGE: English LEVEL: 2
ECTS CREDITS: 6.0 YEAR: 4 SEMESTER: SC
2. LECTURER BASIC INFORMATION
NAME: ORTEGA ALVARADO, LIDIA Mª
DEPARTMENT: U118 - INFORMÁTICA
FIELD OF STUDY: 570 - LENGUAJES Y SISTEMAS INFORMÁTICOS
OFFICE NO.: A3 - 140 E-MAIL: lidia@ujaen.es P: 953212890
WEBSITE: www4.ujaen.es/~lidia
ORCID: https://orcid.org/0000-0002-7320-7382
LANGUAGE: English LEVEL: 2
3. CONTENT DESCRIPTION

  1. Lesson 1: Geometric data types in 2D 
    1. Classes of geometric data
  2. Lesson 2: Geometric data types in 3D
    1. Classes of geometric data
  3. Lesson 3: Spatial data structures
    1. Definition and creation of spatial data structures in 2D and 3D : Grids, kd-trees, range-trees, quadtrees, octrees, etc.
    2. Basic functions
  4. Lesson 4: Programming paradigms for geometric algorithms:
    1. Divide and conquer, Incremental and Sweep line
    2. The particular caso of the convex hull
  5. Lesson 5: Intersections
    1. Intersections of planes, segments lines and polygons
    2. Sweep line for intersection of segment lines
  6. Lesson 6:Location and proximity problems
    1. Point enclosure
    2. The Voronoi diagram.
  7.  Lesson 7: Tessellations
    1. PSLG
    2. Cloud points: triangulations, Delaunay
  8. Lesson 8: Collision detection and visibility
    1. Data structure and algorithms for collision detection: wide and narrow phases.
    2. Data structure and algorithms for visibility.
    3. Hidden surface removal,  Ray-shooting.
  9. Lesson 9: A plication to GIS, collision detection and visibility
    1. Vectorial and raster terrain definition
    2. Algorithms for terrain management and model transformation 

4. COURSE DESCRIPTION AND TEACHING METHODOLOGY

The methodology consists ofthe following activities:

  • Lectures: presentation of theoretical concepts and problem-solving exercises. 
  • Practical sessions:  scheduling algorithms and applications for solving geometric problems. 
  • Collective tutorials:  solving exercises and doubts. 

Students with special educational needs should contact the Student Attention Service (Servicio de Atención y Ayudas al Estudiante) in order to receive the appropriate academic support

5. ASSESSMENT METHODOLOGY

The subject is exceeded if the total count of all parts detailed in the Evaluation System has a value equal to or greater than 5 points.

Furthermore, the class attendance must be at least 50% of the total number of theoretical and practical classes. The theoretical exam must score at least 4 points, computing 30% of the final score. This exam evaluates competences CC6 and CC7 and learning results R3 y R4.

The practical exercises could be done in pairs, except any of them which should be performed individually. The evaluation of the practical part will be performed by submission and defense of the work with the score of the 50% of the subject. This part evaluates competences CC6 and CC7 and learning results R3, R4 and R5.

Throughout the course a set of of theoretical and theoretical-practical exercises are proposed,  counting 10% of the total grade. This part evaluates competences CC6 and CC7 and learning results R3, R4 and R5.

The regular attendance and class participation counted another 10%.

6. BOOKLIST
MAIN BOOKLIST:
  • Computational geometry and computer graphics in C++. Edition: -. Author: Laszlo, Michael J.. Publisher: Upper Saddle River: Prentice Hall, cop. 1996  (Library)
  • Computational Geometry: Algorithms and Applications. Edition: 3rd ed.. Author: -. Publisher: Berlin [etc.] : Springer-Verlag, 2008  (Library)
  • Computational geometry in C. Edition: 2nd ed. Author: O'Rourke, Joseph. Publisher: Cambridge: Cambridge University Press, 2001  (Library)
ADDITIONAL BOOKLIST:
  • Spatial tessellations: concepts and applications of Voronoi diagrams. Edition: 2nd ed. Author: -. Publisher: Chichester [etc.]: John Wiley & Sons, cop. 2000  (Library)
  • Geometric tools for computer graphics [Recurso electrónico]. Edition: -. Author: Schneider, Philip J.. Publisher: Amsterdam ; Boston : Morgan Kaufmann Publishers, 2003.  (Library)
  • Practical algorithms for 3D computer graphics. Edition: -. Author: Ferguson, R. Stuart. Publisher: Natick (Massachusetts): A K Peters, 2001  (Library)
  • Foundations of multidimensional and metric data structures . Edition: -. Author: Samet, Hanan. Publisher: Amsterdam : Elsevier : Morgan Kaufmann, cop. 2006  (Library)
  • Algorithmic foundations of geographic information systems. Edition: -. Author: -. Publisher: Berlin ; Barcelona [etc.]: Springer, cop. 1997  (Library)