Universidad de Jaén

Menú local

Syllabus 2019-20 - 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: 2019-20
COURSE: Geometric Algorithms
SYLLABUS
1. COURSE BASIC INFORMATION
NAME: Geometric Algorithms
CODE: 13313001 ACADEMIC YEAR: 2019-20
LANGUAGE: English LEVEL: 1
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 - 136 E-MAIL: lidia@ujaen.es P: 953212890
WEBSITE: www4.ujaen.es/~lidia
ORCID: https://orcid.org/0000-0002-7320-7382
LANGUAGE: English LEVEL: 1
3. CONTENT DESCRIPTION

  • Lesson 1: Geometric data types in 2D 
    1. Classes of geometric data
  • Lesson 2: Geometric data types in 3D
    1. Classes of geometric data
  • Lesson 3: Intersections
    1. Intersection of planes, segments and polygons
    2. Sweet plane method
  • Lesson 4: Spatial data structures
    1. Definition and creation of spatial data structures in 2D and 3Ds : Grids, kd-trees, range-trees, quadtrees, octrees, etc.
    2. Basic functions
  • Lesson 5: Programming paradigms for geometric algorithms:
    1. Divide and conquer, Incremental and Sweep line
    2. The particular caso of the convex hull
  • Lesson 6:Location and proximity problems
    1. Point enclosure
    2. The Voronoi diagram.
  •  Lesson 7: Tessellations
    1. PSLG
    2. Cloud points: triangulations, Delaunay
  • 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.
  • 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 of the following activities:

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

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

In response to the provisions of art. 13 of the Regulation of Academic Regime and Evaluation of the students of the University of Jaén, the evaluation of the subject will be global.

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 CC6R and CC7R 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 60% of the subject. This part evaluates competences CC6R and CC7R, as well as CB2R, CB3R and CB5R. The learning results are R3, R4 and R5.

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

The regular attendance and class participation counted another 5%.

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: Berg, Mark. 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: Atsuyuki Okabe; Barry Boots; Kokichi Sugihara; Sung Nok Chiu. 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: Marc van Kreveld, Jürgen Nievergelt y Thomas Roos. Publisher: Berlin ; Barcelona [etc.]: Springer, cop. 1997  (Library)