Note: This unit is an archived version! See Overview tab for delivered versions.

COMP5045: Computational Geometry (2012 - Semester 1)

Download UoS Outline

Unit: COMP5045: Computational Geometry (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Postgraduate
Faculty/School: School of Computer Science
Unit Coordinator/s: Dr Gudmundsson, Joachim
Session options: Semester 1
Versions for this Unit:
Site(s) for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: None.
Brief Handbook Description: In many areas of computer science - robotics, computer graphics, virtual reality, and geographic information systems are some examples - it is necessary to store, analyse, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: we study techniques and concepts needed for the design and analysis of geometric algorithms and data structures. Each technique and concept will be illustrated on the basis of a problem arising in one of the application areas mentioned above.
Assumed Knowledge: Students are assumed to have a basic knowledge of the design and analysis of algorithms and data structures: you should be familiar with big-Oh notations and simple algorithmic techniques like sorting, binary search, and balanced search trees.
Lecturer/s: Dr Gudmundsson, Joachim
Timetable: COMP5045 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Project Work - in class 12.00 1 13

Attributes listed here represent the key course goals (see Course Map tab) designated for this unit. The list below describes how these attributes are developed through practice in the unit. See Learning Outcomes and Assessment tabs for details of how these attributes are assessed.

Attribute Development Method Attribute Developed
In the four assignments the focus is on problem solving by applying and modifying algorithmic tools in computational geometry. Design (Level 4)
The ability analyze exciting solutions and to state a correctness proof. Maths/Science Methods and Tools (Level 3)
Ability to present an algorithm and argue its correctness. Communication (Level 3)

For explanation of attributes and levels see Engineering & IT Graduate Outcomes Table.

Learning outcomes are the key abilities and knowledge that will be assessed in this unit. They are listed according to the course goal supported by each. See Assessment Tab for details how each outcome is assessed.

Design (Level 4)
1. Attack theoretical and practical problems in various application domains.
2. Ability to read, understand, analyze and modify a given algorithm. Ability to design algorithmic solutions for given geometric problems.
3. Ability to analyze the complexity of a given algorithm
Maths/Science Methods and Tools (Level 3)
4. Understand and apply important techniques and results in computational geometry.
5. Knowledge of fundamental algorithms for several problems, for example algorithms to compute convex hulls, triangulate polygons, low-dimensional linear programming and Voronoi diagrams Knowledge of fundamental general algorithmic design techniques, such as greedy, dynamic programming and divide-and-conquer.
6. Knowledge of fundamental geometric data structures such as, data structures for range searching, point location, segment intersection and ray shooting.Knowledge of fundamental general design techniques for data structures, such as multi-level trees, duality and divide-and-conquer.
Communication (Level 3)
7. Argue the correctness and efficiency of a proposed solution. Mainly in writing but also orally.
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Assignment No 25.00 Week 4 5, 6, 7,
2 Assignment No 25.00 Week 7 2, 5, 6, 7,
3 Assignment No 25.00 Week 11 4, 5, 6,
4 Final Exam No 25.00 Exam Period 2, 3, 4, 7,
Assessment Description: Assignment: Assignment 1

Assignment: Assignment 2

Assignment: Assignment 3

Assignment: Assignment 4

Assignment: Assignment 5

Assignment: Assignment 6

Exam: To pass the course a minimum of 50% is required on the exam
Grading:
Grade Type Description
Standards Based Assessment Final grades in this unit are awarded at levels of HD for High Distinction, DI (previously D) for Distinction, CR for Credit, PS (previously P) for Pass and FA (previously F) for Fail as defined by University of Sydney Assessment Policy. Details of the Assessment Policy are available on the Policies website at http://sydney.edu.au/policies . Standards for grades in individual assessment tasks and the summative method for obtaining a final mark in the unit will be set out in a marking guide supplied by the unit coordinator.
Special Conditions to Pass UoS To pass this unit a minimum of 50% is required in the final exam.
Policies & Procedures: IMPORTANT: School policy relating to Academic Dishonesty and Plagiarism.

In assessing a piece of submitted work, the School of IT may reproduce it entirely, may provide a copy to another member of faculty, and/or to an external plagiarism checking service or in-house computer program and may also maintain a copy of the assignment for future checking purposes and/or allow an external service to do so.

Other policies

Faculty policies regarding academic honesty and plagiarism, special consideration and appeals in Engineering and Information Technologies can be found on the Faculty's policy page at http://www.eng.usyd.edu.au/policies"> http://www.eng.usyd.edu.au/policies. School and Faculty policies are governed by Academic Board resolutions whose details can be found on the Central Policy Online site at http://www.usyd.edu.au/policy/"> http://www.usyd.edu.au/policy/.

Policies regarding assessment formatting, submission methods, late submission penalties and assessment feedback depend on the unit of study. Details of these policies, where applicable, should be found above with other assessment details.
Prescribed Text/s: Note: Students are expected to have a personal copy of all books listed.
  • Computational Geometry: Algorithms and Application
Online Course Content: Blackboard Learn

Note that the "Weeks" referred to in this Schedule are those of the official university semester calendar https://web.timetable.usyd.edu.au/calendar.jsp

Week Description
Week 1 Art gallery theorems and polygon triangulation
Week 2 Sweepline algorithms, convex hulls, lower bounds
Week 3 Line segment intersection and polygon partitioning
Week 4 Linear programming and probabilistic analysis
Assessment Due: Assignment
Week 5 Orthogonal range searching I: kd-tress and range trees
Week 6 Orthogonal range searching II: fractional cascading and interval trees
Week 7 Planar point location
Assessment Due: Assignment
Week 8 Arrangements and duality
Week 9 Voronoi diagrams and Delaunay triangulation
Week 10 Geometric networks: spanners and proximity graphs
Reading material: Dilation and detour in geometric networks
Week 11 Movement analysis: Curve similarity
Assessment Due: Assignment
Week 12 Reading material: The well-separated pair decomposition and its applications
Approximation algorithms: Applications of the WSPD
Week 13 TBA
STUVAC (Week 14) Study week
Exam Period exam week
Assessment Due: Final Exam

Course Relations

The following is a list of courses which have added this Unit to their structure.

Course Year(s) Offered
Bachelor of Advanced Computing/Bachelor of Commerce 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Health) 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Medical Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Computational Data Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Computer Science Major) 2018, 2019, 2020
Bachelor of Advanced Computing (Information Systems Major) 2018, 2019, 2020
Bachelor of Advanced Computing (Software Development) 2018, 2019, 2020
Bachelor of Computer Science and Technology (Honours) 2015, 2016, 2017
Bachelor of Computer Science and Technology (Honours) 2014 2013, 2014
Software Mid-Year 2016, 2017, 2018, 2019, 2020
Software/ Project Management 2019, 2020
Software 2015, 2016, 2017, 2018, 2019, 2020
Software / Arts 2016, 2017, 2018, 2019, 2020
Software / Commerce 2016, 2017, 2018, 2019, 2020
Software / Medical Science 2016, 2017
Software / Music Studies 2016, 2017
Software / Project Management 2016, 2017, 2018
Software / Science 2016, 2017, 2018, 2019, 2020
Software/Science (Health) 2018, 2019, 2020
Software / Law 2016, 2017, 2018, 2019, 2020
Software Engineering (till 2014) 2010, 2011, 2012, 2013, 2014
Software Engineering / Arts 2011, 2012, 2013, 2014
Software Engineering / Commerce 2010, 2011, 2012, 2013, 2014
Software Engineering / Medical Science 2011, 2012, 2013, 2014
Software Engineering / Project Management 2012, 2013, 2014
Software Engineering / Science 2011, 2012, 2013, 2014
Bachelor of Information Technology 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Arts 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Commerce 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Medical Science 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Science 2015, 2016, 2017
Bachelor of Information Technology (Computer Science) 2014 and earlier 2009, 2010, 2011, 2012, 2013, 2014
Information Technology (Computer Science)/Arts 2012, 2013, 2014
Information Technology (Computer Science) / Commerce 2012, 2013, 2014
Information Technology (Computer Science) / Medical Science 2012, 2013, 2014
Information Technology (Computer Science) / Science 2012, 2013, 2014
Information Technology (Computer Science) / Law 2012, 2013, 2014
Bachelor of Information Technology (Information Systems) 2014 and earlier 2010, 2011, 2012, 2013, 2014
Information Technology (Information Systems)/Arts 2012, 2013, 2014
Information Technology (Information Systems) / Commerce 2012, 2013, 2014
Information Technology (Information Systems) / Medical Science 2012, 2013, 2014
Information Technology (Information Systems) / Science 2012, 2013, 2014
Information Technology (Information Systems) / Law 2012, 2013, 2014
Bachelor of Information Technology/Bachelor of Laws 2015, 2016, 2017
Graduate Certificate in Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Graduate Certificate in Information Technology Management 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Computing 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Information Technology Management 2015, 2016, 2017, 2018, 2019, 2020
Graduate Certificate in Information Technology (till 2014) 2012, 2013, 2014
Graduate Diploma in Information Technology (till 2014) 2012, 2013, 2014
Master of Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Master of Information Technology Management 2015, 2016, 2017, 2018, 2019, 2020
Master of IT/Master of IT Management 2015, 2016, 2017, 2018, 2019, 2020
Master of Information Technology (till 2014) 2014
Software/Science (Medical Science Stream) 2018, 2019, 2020

Course Goals

This unit contributes to the achievement of the following course goals:

Attribute Practiced Assessed
Design (Level 4) Yes 22.5%
Maths/Science Methods and Tools (Level 3) Yes 55%
Communication (Level 3) Yes 22.5%

These goals are selected from Engineering & IT Graduate Outcomes Table which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table for details of the attributes and levels to be developed in the course as a whole. Percentage figures alongside each course goal provide a rough indication of their relative weighting in assessment for this unit. Note that not all goals are necessarily part of assessment. Some may be more about practice activity. See Learning outcomes for details of what is assessed in relation to each goal and Assessment for details of how the outcome is assessed. See Attributes for details of practice provided for each goal.