## Syllabus 2022-23 - 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: 2022-23 COURSE: Geometric Algorithms
SYLLABUS
1. COURSE BASIC INFORMATION
 NAME: Geometric Algorithms CODE: 13313001 ACADEMIC YEAR: 2022-23 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 - 140 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

Practical Program:

The practical program will consist of the delivery of a series of practicals throughout the course, with subject matter related to the theoretical concepts. The requirements of the practices are:

• Java/C++ programming language
• Visual programming environment JOgl/Unity/OpenGL/CGAL depending on the subject matter.
• The last internship will be individual

List of practices:

• Practice 1: 2D geometric data types.
Practice 2: Geometric data types in 3D
Practice 3: Triangle models
Practice 4: Spatial data structures
Practice 5: Algorithms for 3D models
Practice 6: Tessellations: voronoy / delaunay
Practice 7: Projects

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:
• GIS Algorithms (SAGE Advances in Geographic Information Science and Technology Series). Edition: primera. Author: Ningchuan Xiao . Publisher: SAGE Publications  (Library)
• 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)
• 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)
7. VIRTUAL / CLASSROOM TEACHING SCENARIO

1) TEACHING METHODOLOGY AND TRAINING ACTIVITIES.

The activities that cannot be carried out in person will be carried out in a blended format with rotating assistance, and the use of videoconference systems, provided that the capacity and infrastructure of the space assigned for teaching the subject allow it.

The polytechnic school may vary the attendance percentage depending on the number of students and the capacity of the classroom / laboratory according to sanitary measures. In the case of less than 100% attendance, there will be periodic rotation of students as determined by this school.

2) EVALUATION SYSTEM

The evaluation system will be face-to-face for the theoretical exam. The presentation and evaluation of the practicals will also be face-to-face.

3) RESOURCES.

The videoconference systems that are available in the spaces that are enabled for teaching will be used, as well as the teaching platform of the University. Activities that cannot be carried out in person will be carried out through synchronous and / or asynchronous activities carried out through the virtual teaching platform.

8. VIRTUAL TEACHING SCENARIO

1) TEACHING METHODOLOGY AND TRAINING ACTIVITIES.

Activities that cannot be carried out in person will be carried out through synchronous and / or asynchronous activities carried out through the virtual teaching platform and the mechanisms that the University allows or enables.

2) EVALUATION SYSTEM.

The evaluation system and instruments will be the same as for the face-to-face modality, replacing the face-to-face tests with similar tests developed through the use of the online teaching platform or others that the University allows or enables, provided that the identity of the student is guaranteed.

3) RESOURCES.

Activities that cannot be carried out in person will be carried out through synchronous and / or asynchronous activities carried out through the virtual teaching platform.

DATA PROTECTION CLAUSE (on line exams)

Institution in charge of data processing: Universidad de Jaén, Campus Las Lagunillas, s/n, 23071 Jaén

Data Protection Delegate: dpo@ujaen.es

Purpose: In accordance with the Universities Law and other national and regional regulations in force, carrying out exams and assessment tests corresponding to the courses students are registered in. In order to avoid frauds while sitting the exam, the exam will be answered using a videoconference system, being able the academic staff of the University of Jaén to compare and contrast the image of the person who is answering the exam with the student's photographic files. Likewise, in order to provide the exam with evidential content for revisions or claims, in accordance with current regulation frameworks, the exam will be recorded and stored.

Legitimacy: compliance with legal obligations (Universities Law) and other national and regional regulations currently in force.

Addressees: service providers who are the owners of the platforms where the exams are carried out and with whom the University of Jaén has signed the corresponding data access contracts.

Storage periods: those established in current in force regulations. In the specific case of exam videoconference recordings, not before the examination records and transcripts are closed or the exam can still be reviewed or challenged.

Rights: you can exercise your right of access, amendment, cancellation, opposition, suppression, limitation and portability by sending a letter to the postal or electronic address indicated above. In the event that you consider that your rights have been violated, you may submit a complaint to the Andalusian Council for Transparency and Data Protection www.ctpdandalucia.es

CLASS RECORDING CLAUSE PERSONAL DATA PROTECTION

Person in charge: Universidad de Jaén, Paraje Las Lagunillas, s/n; Tel.953 212121; www.ujaen.es

Data protection delegate (DPO): TELEFÓNICA, S.A.U. ; Email: dpo@ujaen.es

Procedure aim: To manage proper recordings of teaching sessions with the aim of facilitating learning process under a multimodal and/or online teaching

Period for record storage: Images will be kept during legal term according to regulations in force

Legitimacy: Data will be managed according to legal regulations (Organic Law 6/2001, December 21, on Universities) and given consent provided by selecting corresponding box in legal admission documents

Data recipients (transfers or assignments): Any person allowed to get access to every teaching modality

Rights: You may exercise your rights of access, rectification, cancellation, portability, limitation of processing, deletion or, where appropriate, opposition. To exercise these rights, you must submit a written request to the Information, Registration and Electronic Administration Service of the University of Jaen at the address above, or by e-mail to the address above. You must specify which of these rights you are requesting to be satisfied and, at the same time, you must attach a photocopy of your ID card or equivalent identification document. In case you act through a representative, legal or voluntary, you must also provide a document that proves this representation and identification. Likewise, if you consider that your right to personal data protection has been violated, you may file a complaint with the Andalusian Data Protection and Transparency Council www.ctpdandalucia.es