COMP SCI 4402 - Introduction to Geometric Algorithms

North Terrace Campus - Semester 2 - 2017

Introduction to Computational Geometry techniques. Topics include theoretical and applied aspects of computational geometry

  • General Course Information
    Course Details
    Course Code COMP SCI 4402
    Course Introduction to Geometric Algorithms
    Coordinating Unit School of Computer Science
    Term Semester 2
    Level Undergraduate
    Location/s North Terrace Campus
    Units 3
    Contact Up to 2 hours per week
    Available for Study Abroad and Exchange Y
    Prerequisites COMP SCI 2201
    Assumed Knowledge Discrete mathematics such as in MATHS 1008
    Course Description Introduction to Computational Geometry techniques. Topics include theoretical and applied aspects of computational geometry
    Course Staff

    Course Coordinator: Dr Tat-Jun Chin

    Lecturers A/Prof Gustavo Carneiro and Dr. Javen Shi
    Course Timetable

    The full timetable of all activities for this course can be accessed from Course Planner.

  • Learning Outcomes
    Course Learning Outcomes
    (1) Understanding of basic concepts of computational geometry and standard algorithms such as plane sweeping, linear programming, voronoi diagrams and Delaunay Triangulation.
    (2) Understanding of basic principles and theory of geometric algorithms, which may guide students to develop their own algorithms for solving geometric problems.
    (3) Ability to implement the algorithms in the course.
    (4) Ability to do mathematical derivation of the algorithms in the course.
    University Graduate Attributes

    This course will provide students with an opportunity to develop the Graduate Attribute(s) specified below:

    University Graduate Attribute Course Learning Outcome(s)
    Deep discipline knowledge
    • informed and infused by cutting edge research, scaffolded throughout their program of studies
    • acquired from personal interaction with research active educators, from year 1
    • accredited or validated against national or international standards (for relevant programs)
    Critical thinking and problem solving
    • steeped in research methods and rigor
    • based on empirical evidence and the scientific approach to knowledge development
    • demonstrated through appropriate and relevant assessment
    Teamwork and communication skills
    • developed from, with, and via the SGDE
    • honed through assessment and practice throughout the program of studies
    • encouraged and valued in all aspects of learning
    Career and leadership readiness
    • technology savvy
    • professional and, where relevant, fully accredited
    • forward thinking and well informed
    • tested and validated by work based experiences
    Intercultural and ethical competency
    • adept at operating in other cultures
    • comfortable with different nationalities and social contexts
    • Able to determine and contribute to desirable social outcomes
    • demonstrated by study abroad or with an understanding of indigenous knowledges
    Self-awareness and emotional intelligence
    • a capacity for self-reflection and a willingness to engage in self-appraisal
    • open to objective and constructive feedback from supervisors and peers
    • able to negotiate difficult social situations, diffuse conflict and engage positively in purposeful debate
  • Learning Resources
    Required Resources
    The main textbook used in the course is M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. This book is available online through the University of Adelaide library.
    Online Learning
    All course material including lecture sildes, assignment instructions, and lecture recordings, are available from the course homepage:
    The course forum is accessible via:
  • Learning & Teaching Activities
    Learning & Teaching Modes
    The course will be primarily delivered through two activities:
    - Lectures
    - Assignments
    Lectures will introduce and motivate the basic concepts of each topic. Significant discussions and two-way communication are also expected during lectures to enrich the learning experience. The assignments will reinforce concepts by their application to problem solving. This will be done via programming work, and mathematical derivation. All material covered in the lectures, and assignments are assessable.

    The information below is provided as a guide to assist students in engaging appropriately with the course requirements.

    The information below is provided as a guide to assist students in engaging appropriately with the course requirements.
    This is a 3-unit course. Students are expected to spend about 8 hours per week on the course. This includes a 2-hour lecture, 2-hour self study and up to 4 hours per week on completing assignments.
    Assigmment work will be subjected to deadlines. Students are expected to manage their time effectively to allow timely submission, especially with consideration to workload of other courses.
    Learning Activities Summary
    Students are encouraged to attend lectures as material presented in lectures often includes more than is on the slides. Students are also encouraged to ask questions during the lectures. Slides and lecture recordings will be available via the subject web page.

     Week          Date     Topic     Lecturer     Assignment   
    1   29/07/2016    Computational Geometry - Introduction GC
    2 05/08/2016 Line Segment Intersection - Thematic Map Overlay GC
    3 12/08/2016 Line Segment Intersection cont. GC Assignment 1 (due on 26/08)
    4 19/08/2016 Polygon Triangulation - Guarding an Art Gallery GC
    5 26/08/2016 Linear Programming - Manufacturing with Molds GC
    6 02/09/2016 Linear Programming cont. GC Assignment 2 (due on 16/09)
    7 09/09/2016 Orthogonal Range Searching - Querying a Database GC
    8 16/09/2016 Orthogonal Range Searching cont. GC
    9 07/10/2016 Point Location - Knowing Where You Are JS
    10 14/10/2016 Voronoi Diagrams - The Post Office Problem JS Assignment 3 (due on 28/10)
    11 21/10/2016 Voronoi Diagrams - continued JS
    12 28/10/2016 Delaunay Triangulations - Height Interpolation GC Assignment 4 (due on 11/11)
    Specific Course Requirements
    Knowing some basic mathematics and linear algebra would be helpful, but not essential. They will be covered when needed.
    Ability to program in Matlab is required.
  • Assessment

    The University's policy on Assessment for Coursework Programs is based on the following four principles:

    1. Assessment must encourage and reinforce learning.
    2. Assessment must enable robust and fair judgements about student performance.
    3. Assessment practices must be fair and equitable to students and give them the opportunity to demonstrate what they have learned.
    4. Assessment must maintain academic standards.

    Assessment Summary
    The course includes the following assessment components:
    Four assignments at 25% each.  Each assignment involves all four learning objectives.
    Assessment Related Requirements
    Students must obtain at least 50% of the overall marks to pass the course.
    Assessment Detail
    Each student is expected to complete assignments in the form of report and programming work. The assignments must be completed individually and all submissions are to be made under the declaration of adherring to the academic honesty principles. Submissions will be subjected to plagiarism checks. This course has a zero-tolerance policy towards academic honesty violations. Offenders will be duly subjected to University procedures for dealing with academic honesty cases.

    Assessment Type Proportion of that
    Due week Learning

    Problem Solving
    CBOK Mapping

    Problem Solving

    Technology building
    Assessment 1 Formative
    and Summative
    25% week 5 1,2,3,4 3 3 5
    Assessment 2 Formative
    and Summative
    25% week 8 1,2,3,4 3 3 5
    Assessment 3 Formative
    and Summative
    25% week 11 1,2,3,4 3 3 5
    Assessment 4 Formative
    and Summative
    25% week 14 1,2,3,4 3 3 5

    Due Dates: The assignment due dates will be made available on the course website.
    *CBOK categories are explained in section 4 of the ICT core body of knowlege. Numbers assigned correspond to the Bloom taxonomy (see page 26 of the same document).
    Assignment solutions are to be submitted through the School of Computer Science's Moodle forum:
    No physical submissions of work will be accepted unless specifically requested by the lecturer.
    Marks will be capped for late submissions, based on the following schedule:
    1 day late – mark capped at 75%
    2 days late – mark capped at 50%
    3 days late – mark capped at 25%
    more than 3 days late – no marks available.
    Extensions to due dates will only be considered under exceptional medical or personal conditions and will not be granted on the last day due, or retrospectively. Applications for extensions must be made to the course coordinator by e-mail or hard copy and must include supporting documentation – medical certificate or letter from the student counselling service.
    Course Grading

    Grades for your performance in this course will be awarded in accordance with the following scheme:

    M10 (Coursework Mark Scheme)
    Grade Mark Description
    FNS   Fail No Submission
    F 1-49 Fail
    P 50-64 Pass
    C 65-74 Credit
    D 75-84 Distinction
    HD 85-100 High Distinction
    CN   Continuing
    NFE   No Formal Examination
    RP   Result Pending

    Further details of the grades/results can be obtained from Examinations.

    Grade Descriptors are available which provide a general guide to the standard of work that is expected at each grade level. More information at Assessment for Coursework Programs.

    Final results for this course will be made available through Access Adelaide.

  • Student Feedback

    The University places a high priority on approaches to learning and teaching that enhance the student experience. Feedback is sought from students in a variety of ways including on-going engagement with staff, the use of online discussion boards and the use of Student Experience of Learning and Teaching (SELT) surveys as well as GOS surveys and Program reviews.

    SELTs are an important source of information to inform individual teaching practice, decisions about teaching duties, and course and program curriculum design. They enable the University to assess how effectively its learning environments and teaching practices facilitate student engagement and learning outcomes. Under the current SELT Policy ( course SELTs are mandated and must be conducted at the conclusion of each term/semester/trimester for every course offering. Feedback on issues raised through course SELT surveys is made available to enrolled students through various resources (e.g. MyUni). In addition aggregated course SELT data is available.

  • Student Support
  • Policies & Guidelines
  • Fraud Awareness

    Students are reminded that in order to maintain the academic integrity of all programs and courses, the university has a zero-tolerance approach to students offering money or significant value goods or services to any staff member who is involved in their teaching or assessment. Students offering lecturers or tutors or professional staff anything more than a small token of appreciation is totally unacceptable, in any circumstances. Staff members are obliged to report all such incidents to their supervisor/manager, who will refer them for action under the university's student’s disciplinary procedures.

The University of Adelaide is committed to regular reviews of the courses and programs it offers to students. The University of Adelaide therefore reserves the right to discontinue or vary programs and courses without notice. Please read the important information contained in the disclaimer.