CSE 6403: Computational Geometry

Quick Links:     Contact/Course teacher:     Books     Announcements      Marks Distribution     Study Topics     Web resource     Course syllabus and Schedule     Presentation     Project     Final Exam     Bonus     Open Problems     Exercise

Contact/Course teacher:

Dr. Masud Hasan

Assistant Professor

Department of CSE, BUET

Office: CSE 657

Phone: 8614640-44, Ext. 7738

Email: masudhasan "at" cse "dot" buet "dot" ac "dot" bd

Course web: http://203.208.166.84/masudhasan/cse6403_Nov_07.html

Books:

1. Computational Geometry: Algorithms and Applications, by de Berg, van Kreveld, Overmars, and Schwarzkopf, 2nd Edition. [Available in Nilkhet]

2. Computational Geometry in C, by Joshep O'Rourke, 2nd edition. [Available in BUET Library and Nilkhet]

Announcements:

• Project submission deadline: Submit your project by 28/3/2008, Friday. Slide under my office door or put into my box.

• 27/11/2007: No more class before Eid. Have a nice Eid!

Marks distribution:

Active participation in the class: 20%

Select a study topic and give a presentation on that: 20%

Write a project on that topic: 20%

Final exam: 40%

Bonus: depending upon the level of work in finding any new result on your research topic or an open problem mentioned in the class.

Study topics:

You have to spend some time for selecting your topic first. I will suggest a list of topics. Most of these topics are very vast. First you may choose a topic according to your interest. Then read one/two papers (or more if necessary) and select your topic from there. Once you have selected your topic explore other papers by going through the references of your initial papers and the paper where they have been referred. Citeseer or IEEE Explorer will help you a lot to get most of the papers online and to find the earlier and following papers. Throughout your adventure on the papers you should identify the important papers and the results therein.

You will select topics individually or in pair. One topic may be chosen by more than one individual/pair. You may also suggest topics of your own and verify with me. Throughout the course you will study this topic in detail. You will give a presentation (if in pair, then two presentations) and write a project (one project even in a pair). You have to find recent results on this topic and will try to find new results. You will present your findings by the presentation and by your project. If you can find any new result on your/others topic or on any open problem mentioned in the class you will get some bonus marks on top of your total marks. Below are some possible topics with brief description. I have also added one/two papers/references with each topic with which you can start. But be careful of any kind of plagiarism. That means, DO NOT USE these resources for any kind of copy or cut and paste.

Possible topics/papers for finding a study topic: [You need GhostView to view ps files]

Come to me if you find any paper yourself.

1. Art gallery problem, part I: This is an application of polygon triangulation. This topic has been studied extensively with lot o variation. The following paper is a quite old paper but discusses lot of variations. Use it to find recent results. Paper: Art Gallery and Illumination Problems, Jorge Urrutia (Part I: up to Section 5)

2. Art gallery problem, part II: Same as 1. Paper: Art Gallery and Illumination Problems, Jorge Urrutia (Part II: Section 6 - rest)

3. Jordan sorting in linear time: This is very much related to polygon triangulation. Paper: Simplified Linear-time Jordan Sorting and Polygon Clipping, K.Y. Fung, T.M. Nicholl, R.E. Tarjan, C.J. Van Wyk [pdf]

4. Medial Axis: This is a generalization of Voronoi diagram. Paper: Finding the medial axis of a simple polygon in linear time, F. Chin, J. Snoeyink, and A. Wang, Discrete Computational Geometry 21:405-420 [pdf]

5. Protein folding: This is a new topic of bioinformatics. It will involve 3D concept. Papers: These papers may not be the right papers for you but their introduction will lead you to other convenient papers (i) Geometric Restrictions on Producible Polygonal Protein Chains, (ii) Long Proteins with Unique Optimal Foldings in the H-P Model, (iii) On the complexity of protein folding, (iv) Fitting protein chains to cubic lattice is NP-Complete [pdf].

6. Computational geometry in wireless network: Survey the applications of computational geometry in wireless network and find the algorithmic open problems there. You will find numerous papers in this topic. You can visit the publications of some researchers in this field: Jia Gao, Ivan Stojmenovic.

7. Variations of Voronoi diagram and Delaunay triangulations: There are lot of variations of Voronoi diagram and Delaunay triangulations and they are practical application motivated. Some important variations are: power diagram, medial axis (already mentioned in 4), straight skeleton. Voronoi diagram on the sphere, Voronoi diagram of polygonal site, furthest site Voronoi diagram, etc. Some variations exist for Delaunay triangulation too. You may start with visiting Voronoi related papers by these people: Otfried Cheong, Tetsuo Asano, Kokichi Sugihara.

   Also you can first read the survey article: Voronoi diagrams.

8. 3D graph drawing: Drawing graphs in 3D with different criteria, such as minimum bends of edges, minimum volume of the drawing, etc. Visit the publications of David R. Wood.

9. Recent developments in convex hull algorithms. Convex hull is one of the most studied topic in computational geometry. There are many variations of convex hull algorithm. Visit the convex hull related publications of Timothy Chan, Hervé Brönnimann,

10. Recent developments in geometric shortest path algorithms: Start with this paper Geometric Shortest Paths and Network Optimization. Also visit the publications of Joshep Mitchell for more recent developments.

11. Geometric morphing: Morphing means converting one shape to other. Visit the publications of Michael Spriggs and Anna Lubiw

12. Computational geometry soft wares: Are you already bored with too much theory? Then go for geometry software. While most computational geometers work on theory, robust implementation of algorithms is a challenge. That's why geometry software are also of great interest to computational geometers. In this topic you have to focus on the difficulties of implementation, available soft wares and libraries, their features, etc. Some links: CGAL,  LEDA, GDToolkit; also search by "computational geometry software".

Web resources:

Be careful of any kind of plagiarism. That means, DO NOT USE these resources for any kind of copy or cut and paste. Use them to find research topics and related papers. But make your presentation and write your project yourself.

• The Geometry Junkyard, maintained by David Eppstein

• Geometry in Action, maintained by David Eppstein

• Computational Geometry Resources

• Computational Geometry Pages

• Open Problem Project: The open problems in computational geometry, maintained by Joshep O'Rourke and Erik Demaine.

Active participation in the class [20%]:

You will get this if you actively participate in the class, where by an "active participation" means you come to the class in time, turn your mobile off, attentively listen, ask (logical) questions, give comments, etc. It is not necessary that you ask questions or give comments all the time; even, your body language without any verbose participation may indicate you are very much attentive in the class.

Presentation [20%]:

Follow the guidelines below in your presentation.

• Complete your presentation within 15-20 minutes

• Clearly explain what the topic is

• Describe the research problems in this topic

• Application of this topic

• Related work done so far (should be recent works)

• Future work possible (as it comes to your mind and as it is mentioned in related papers)

• Direction of the project that you will do on this topic

• Selecting a good topic will also carry marks

• Remember that this is a graduate course. So try to make your presentation attractive, informative, and friendly. Try to become less formal and communicative with the audience.

• You may visit "How to give a good presentation" here: http://203.208.166.84/masudhasan/

Course syllabus and Schedule: [Syllabus is now final]

Time: Tuesday 5:00pm to 8:00pm

Location: Room no CSE 502

We will try to cover the following topics as per the following tentative sequence:

Project [20%]:

As mentioned earlier, project will be the written form of what you find on your topic. It must be written in latex, report size is expected to be within10 to 15 pages with 11 fonts and single spacing. You can collect latex installation files from me (~450 MB).

Final exam [40%]:

Bonus:

If you can find any new result on your/others topic or on any open problem mentioned in the class you will get some bonus marks on top of your total marks.

Open Problems:

1. Find a simple linear time algorithm for triangulating a simple polygon.

2. Sort a Jordan sequence without finger search tree.

Excercise:

1. Prove the "output sensitive" W(n log h) lower bound of convex hull in 2D?