Geometric Algorithms

Code:

CC443

Acronym:

CC443

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2013/2014 - 2S

Active?	No
Web Page:	http://www.dcc.fc.up.pt/~apt/aulas/ALGOGEO/1314
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master's Degree in Network and Information Systems Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	0	PE do Mestrado em Ciência de Computadores	1	-	7,5	67	202,5
MI:ERS	0	Plano de Estudos a partir de 2007	4	-	7,5	67	202,5

Teaching language

Portuguese

Objectives

An introduction to fundamental algorithms and data structures in planar Computational Geometry  with applicatons in Computer Graphics, Computer Aided Design, Geographic Information Systems, Molecular Biology and Data Analysis.

Learning outcomes and competences

At the end of this course, students shoud know and be able to implement efficient algorithms and data structures for solving fundamental geometric problems in the plane, or adapt them to solve related problems.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Background on Design and Analysis of Algorithms and Programming Languages (C, C++, JAVA or Python).

Program

Fundamental concepts and tools in computational geometry.
Plane-sweep algorithms. Convex-hulls. Geometric data structures. Polygon
decomposition. Triangulations. Visibility in the plane. Art Gallery Problems. Line segment
intersections. Subdivision overlay. Arrangements. Point Location and proximity. Voronoi
diagrams and Delaunay triangulations. Applications.

Mandatory literature

000075502. ISBN: 978-3-540-65620-3 hbk
000074637. ISBN: 0-521-64976-5

Complementary Bibliography

000097672. ISBN: 9780444825377
000097671. ISBN: 9781584883012
000102107. ISBN: 9780262033848 hbk
000000083. ISBN: 978-0-387-96131-6 New York : hbk

Teaching methods and learning activities

Lectures with discussion of case study examples of application of the algorithms presented. Lab classes for developing a practical project. Written and oral presentation of the projects by students.

Final Grade: 35% Project (to study and implement an algorithm for solving a geometric problem about a topic to be defined by the lecturer). 65% Final exam (questions about the topics and algorithms addressed).

 

 

 

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	65,00
Participação presencial	0,00
Trabalho laboratorial	35,00
Total:	100,00

Eligibility for exams

Students who miss more than 25% of lab lessons cannot take the final exam.

Calculation formula of final grade

35% Project (Implementation + Report)

65% Final exam (grade >= 9.5 / 20)

Special assessment (TE, DA, ...)

The same for all the students enrolled.