CSE 6403: Computational Geometry

April 2009 Semester

Quick Links:     Contact/Course teacher:     Text     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, 9665650-80, Ext. 7738

Email: masudhasan at cse.buet.ac.bd, mhasan2010 at gmail.com, mhasan2010 at yahoo.com

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

 

Text:

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

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

Announcements:

 

New !!! Project submission deadline: 07/09/2009 (Monday) 12:00 midnight; hard copy only, no soft copy; keep in my office box or slide under my office door (Room no CSE 657).

 

Marks distribution:

Active participation in the class: 10%

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

Write a project on that topic: 20%

Final exam: 50%

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 topics in the class as I move on. You may first 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, IEEE Explorer, and Google Scholar 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. If you do not find a paper that you really need, then send me the link.

 

You will select topics individually or in pair (I suggest for pairing). One topic may not 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 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.

 

Finally, you can try to find your graduate thesis topic through these study topics :-)

 

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

  1. [Taken by Jawaherul, ...] Study the recent developments in Art Gallery Theory and Algorithms: There are a huge number of variations of the problem. You will find many surveys and an entire book by O'Rourke online. But you have to deal with the most recent results.

  2. Study why finding a simple linear time algorithm is so difficult and find the relation of this problem to the linear time Jordan sorting, which uses complex data structure like finger search trees.

  3. [Taken by Wasiur +  Nusrat] Voronoi games in competitive facility location

  4.  [Taken by Sukorno + Arup, Nashid + Popel] Concept of Voronoi games in ad-hoc/sensor network

  5. O(n) time algorithm for medial axis: study the algorithm; try to find out whether it would be possible to device an O(n) algorithm without first using the complicated Chazelle's O(n) triangulation algorithm.

  6. [Same as 11] Computational Geometry + Data Mining/Pattern Search: See how you like the papers in this project page.

  7. [Taken by 0409052030, 0409052032] Geometric Spanners: This is a new topic of research in computational geometry, but it is very vast. There is an entire book on it. You need to give the idea of it only and to survey some very recent results on a particular subtopic.

  8. [Taken by 0409052031, 0409052071] Coverage in wireless sensor network using Voronoi diagram: Study how Voronoi Diagram is so useful in wireless sensor network coverage. Start with these three papers.

  9. [Taken by 0409052016, 0409052042] Antenna Cover: This topic will deal with, in abstract sense, finding minimum circle range to cover a set of point. It uses, once again, Voronoi diagram. Start with this paper.

  10. [Taken by 0409052033, 0409052081] Coresets: New topic, recently addressed by many famous researchers, mainly used for approximation algorithms for geometric problems. You can start with this survey of Pankaj Agarwal et al.

  11. [Taken by .... ] Geometry of spatio-temporal data: Has relation with data mining. Come to my office to have some papers on it.

  12. [Taken by 0409052073, Sabrina] Geometry of spatio-temporal data in 3D

  13. [Taken by 0409052049, 0409052059] Place a convex polygon inside a circle so that the cutting cost is optimal.

  14. [Taken by Shuvra + Mahfuza]  3D Voronoi diagram for protein folding.

  15. [Taken by Jesmin Jahan] Molecule shape matching: Start with this paper.

  16. [Assigned to Shahrear Iqbal + ...] Geometric Softwares: This topic will bring some change if you are already bored with too much theory! While most computational geometers work on theory, robust implementation of algorithms is a challenge. That's why geometry softwares are also of great interest to computational geometers. In this topic you have to focus on the difficulties of implementation of algorithms, available softwares 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. Use them to find research topics and related papers. But make your presentation and write your project yourself.

Some good conferences on Computational Geometry: Almost all algorithm and theory conferences ask paper on computational geometry. Some specific conferences on computational geometry are

Some good journals on Computational Geometry: Almost all algorithm and theory journals accept papers on computational geometry. Some specific journals on computational geometry are

Active participation in the class [10%]:

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%]:

You must make your presentation in Beamer.

Follow the guidelines below in your presentation.

Course syllabus and Schedule:

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

Location:

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

 

Date, Lecture # Topics Presentation schedule
5/5/2009, Lecture 1

  • Introduction, policies

  • Art gallery theorem, Theory of polygon triangulation (O'Rourke Ch 1.1, 1.2)

  • Algorithms for polygon triangulation (O'Rourke Ch 2.1-2.3, de Berg Ch 3.1, 3.3)

  
12/5/2009, Lecture 2

  • Convex hull in 2D (de Berg Ch 1, O'Rourke Ch 3.1-3.3, 3.6, Chan's paper)

  
19/5/2009 No Class; Summer Vacation  
26/5/2009, Lecture 3

  • Convex hull in 3D, Convex polyhedra, Euler's formula, Steinitz' theorem (de Berg Ch 11.1, O'Rourke Ch 4.1(except 4.1.2), 4.2.1)

  
2/6/2009, Lecture 4

  • Voronoi diagrams, Delaunay triangulations (de Berg Ch 7.1, 7.3, 9.1, 9.2, O'Rourke Ch 5.1-5.3, 5.4.1-5.4.3, 5.5-5.7.3)

  
9/6/1009, Lecture 5  
16/6/2009, Lecture 6

  • Arrangements and Duality (de Berg Ch 8.1-8.3, O'Rourke Ch 6.1-6.3, no proof for Zone Theorem)

  
23/6/2009, Lecture 7

  • Arrangements and Duality (de Berg Ch 8.1-8.3, O'Rourke Ch 6.1-6.3, no proof for Zone Theorem)

  
30/6/2009 No class !!!  
7/7/2009, Lecture 8

  • Line segment intersection (O'Rourke Ch 7.7, 7.8, de Berg Ch 2.1: Follow class note)

  
14/7/2009, Lecture 9

  • Planar point location (O'Rourke Ch 7.11, de Berg Ch 6.1: Follow class note)

  
21/7/2009, Lecture 10

  • Visibility graph, Shortest path (de Berg Ch 15.1, O'Rourke Ch 8.1, 8.2) (No class: University closed; Eid-E-Miladunnabi)

 
28/7/2009, Lecture 11 Linear Programming

  • Sukorno + Arup

  • Popel + Nashid

  • 0409052031, 0409052071

  • 0409052049, 0409052059

  • 0409052033, 0409052081

  • 0409052016, 0409052042
4/8/09, Lecture 12 Range Searching

  • Wasiur + Nusrat

  • Shuvra + Mahfuza

  • Topic 11

  • 0409052073, Sabrina

  • 0409052030, 0409052032

  • Shahrear Iqbal
11/8/09, Lecture 13 Binary Space Partition

  • Jawaherul + 040805024

  • Maruf Saifullah (Topic 5)

  • Jesmin Jahan (Topic 15)

  • 040805012 + 040805031

  • Saddam

 

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).

Try to arrange your project according to the following guideline:

Final exam [50%]:

 

Date declared: see the notice board

Syllabus: as above

Previous year questions: October 2006, October 2007

 

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:

 

Excercise: