Obligatory Assignment

You must read through the entire page. Rules applying to all the parts of the obligatory assignment can be found below.


The obligatory assignment will be given in parts. The first will cover important techniques that all students should gain experience implementing. A later part will be more individual.

You may do the work yourself or work in pairs, i.e., work is done in groups of 1-2 students. If you would like to work with another student, you just arrange it yourself. There is no official recommendation as to whether or not you choose to work with another student. The implementation work should not be overwhelming for students at your level, so it mostly boils down to whether you find it helpful to discuss issues with a fellow student or if you just find it time-consuming to have to coordinate and meet at specific times that may not fit well into your schedule.

You are not allowed to receive help from anybody not in your group, and you must ensure that other people cannot read your files. If you are working on your own laptop, you are probably used to handling this. If you do the work on the IMADA computers, a good method is to create a new directory, DM819project, for your project files. After having issued the command makedir DM819project, issue the command chmod 700 DM819project.

There are no retries! You have reached a level where you know what it takes to answer an assignment satisfactorily and on time. Blackboard will not accept assignments turned in late.

Part 2

This part has the subtitle "My favorite problem in computational geometry". The intention is that you should be allowed to choose your own problem. This could be an implementation of one of the algorithms in the textbook, one of the algorithms we have considered in the exercises, some other problem from the literature, or even one of your own ideas. The project must be at a reasonable level and have a certain minimum size (no less challenging than part 1), so before you start you must consult the lecturer to have your project idea approved.

The entire group must see the lecturer at the same time for approval of the project idea, programming language, etc. There is no deadline for doing this, but since you cannot start your project before this time, you ought to get this done several weeks prior to the deadline for handing in the project; in particular because your initial project idea might not be approved.

You may work in different groups than you did during part 1 and your overall result will be the combination of the two results you obtained. Thus, even though you and your new partner get the same result on part 2, you and your new partner may get different overall results due to possibly different results in part 1. In conclusion, you will not be punished for working with somebody who got a worse result than you in part 1 (provided of course that the new partner's contribution to part 2 is uncorrelated with the part 1 result).

Here are possible examples of tasks from what we have covered in the first quarter of the course (but talk to the lecturer before you start):

Deadline: Thursday, December 8, 2011, at 23:59.

Part 1

Part 1 of the obligatory assignment is to implement the algorithm described in the textbook, exercise 2.14.

Input to the program is a list of line segments, S, and a query point, p. The output is a list (without duplicates) of all the line segments from S that are visible from p, as defined in the exercise.

You must use the half-line sweep technique suggested in the exercise and obtain the O(n log n) running time. You must use the design philosophy introduced in Chapter 1 of the textbook. So, for the sweep, you should use an event queue and a status. Furthermore, after the design based on input in so-called "general position", you must consider and handle special cases. Your description of your implementation in your report must include a section on how the geometric tests you use are computed. See the rules below for further requirements.

Deadline: Monday, October 3, 2011, at 23:59.


First note that an obligatory assignment is an exam, so rules that apply in an exam situation also apply here.

All parts of the obligatory assignment deal with implementing algorithms from the area of computational geometry. For each part, you must turn in a report and an implementation before the deadline for the given part.

After you have handed in your project, you may with no or very short notice be called in for a brief examination or be asked to demonstrate your program. If this becomes necessary, you will be notified in class or via one of your e-mail addresses. It is your responsibility to check your e-mail regularly. If you do not come in for a necessary meeting before the exam office needs the results, you will not pass.

Implementation Requirements

In your implementations, you are supposed to use the techniques which have been introduced during the course. When implementing algorithms analyzed in the textbook, your implementation must be of the same asymptotic complexity as the corresponding algorithm in the book. There may be additional requirements stated under the specific parts of the obligatory assignment or individual requirements (typically for later project parts).

Your program must be capable of reading all its input from a text file, and you must specify the format and include examples in the report and in test files. Your program must also be capable of outputting the result in text form, e.g., in the form of coordinates for points and lines. Again, you must specify the format and include examples. Additionally, your program must be capable of showing the result graphically. You can choose the method yourself, but it must work on IMADA's computers and be printable. One of the simplest satisfactory ways of doing this is to use LaTeX. There is an example of how this can be done below. It is strongly recommended that you implement graphical printing early in the process, since it makes debugging so much faster. Clearly, you should also describe how your program should be run.

Solutions in the form of programs, data for viewers, etc. must work on IMADA's computers with the compilers and other applications present on IMADA's computers, so that we can test your solution. You are free to develop your solution at home, but it is your own responsibility to transfer your solution to IMADA's system and make the necessary adjustments such that it works at IMADA. You can indicate in your report which IMADA machine you have run your code on to remove any doubt at a later point in time. If you would like to use facilities not available on the IMADA computers, talk to your lecturer as early as possible, and we will see if a solution can be found.

Programming Language

The preapproved programming languages you can choose from are the following: If you have other preferences, you could likely obtain permission to use an alternative. Contact the lecturer.


Many programming languages come with libraries. If you use a programming language where you can use packages, classes, libraries or other code which has been supplied by the programming language developers, you have to know how the facilities included in these modules are implemented such that you can account for the asymptotic complexity.

Overall Report Content

You must document that you have done all that is required, as outlined in the obligatory assignment description and the rules, in the form of a report. It must be possible to evaluate your project from your report alone. You must include a sufficiently detailed description of the problem you solve, an account for the geometric special cases, an account for the geometric calculations used in the implementation, an account for the asymptotic complexity, a convincing test suite demonstrating that your program works (also in special cases), and any additional requirements from the part-description must be handled.

Report Format

The front page of your report must be dated, include your full name, the first 6 digits of your CPR number, IMADA e-mail address, and student e-mail address (nn@student.sdu.dk).

Your report must be in the form of a pdf-file named "report.pdf" which includes all the material (report, program listing, tests, etc.) in one pdf-file (talk to the lecturer if this is a problem), and in addition make programs and test data available in text format as well (thus, you turn in program listing and test data both as part of "report.pdf" and in the original text format). The programs etc. in the original text format must of course be identical to the listing in the report (formatting and adding line numbers and headlines is of course fine).

For may zip all of this together in one file that you can upload via Blackboard. You can use zip, bzip2 or tar (with or without gzip).

All file names should be logical and descriptive. Your report should list all file names and explain what they contain.


Your report must have a section called "Manual". Here you must describe the exact textual input and output format. You must also explain how to compile and run your code on IMADA's computers. Be careful not to hardwire references to you home directory etc. into the code such that it will not be possible for us to compile or run your program directly. You must also explain how to view and print your graphical output. Your goal should be to make it as easy as possible for the lecturer to run your program on additional tests to the ones you have provided.

Turning In

You turn in a printed version of your report on paper to your lecturer's letter box in the secretaries' office and the corresponding electronic version via Blackboard (which will give you a receipt):
  1. Log in and choose this course.
  2. Click on the little box on the top left of the page, just left of the grey field containing a text starting with the course code, and a menu should pop up.
  3. Enlargen the window if it comes up small.
  4. Click "Tools" in the menu, and a number of clickable icons show up to the right of the menu.
  5. Click "Assignment hand in".
  6. Fill in the form and submit.
  7. Print/save your receipt (you should also get one by e-mail).

Pictures in LaTeX

See the example LaTeX file, Example.tex, to see how simple geometric figures can be produced. To process such a file, you write latex Example.tex on the command line. This produces a dvi-file, Example.dvi, which can be viewed using xdvi Example.dvi or printed using dvips -Pd3 Example.dvi. The format can be changed to postscript using dvips Example.dvi -o. This creates a file Example.ps, which can be viewed using gv Example.ps. The format can be changed to pdf using dvipdf Example.dvi. This creates a file Example.pdf, which can be viewed using acroread Example.pdf.

Last modified: Fri Dec 2 15:51:24 CET 2011
Kim Skak Larsen (kslarsen@imada.sdu.dk)