CSE 6403: Computational Geometry
April 2012 Semester
Dr. Masud Hasan
Associate Professor
Department of CSE, BUET
Office: CSE 117
Phone: 8614640-44, Ext. 6113
Email: mhasan2010 "at" gmail "dot" com
Web: http://203.208.166.84/masudhasan/cse-6403-april-2012.html
[O] Computational Geometry in C, by Joshep O'Rourke, 2nd edition. [Available in BUET Library and Nilkhet]
[dB] Computational Geometry: Algorithms and Applications, by de Berg, van Kreveld, Overmars, and Schwarzkopf, 3rd Edition. [Available in BUET Library and Nilkhet]
- All Remaining presentations to be held on November 03, 2012. That's the last class. No more presentations after that class.
Project submission deadline: 3-12-2012 (Monday) 12:00noon. Slide under my office door or put in my pigeonhole in CSE Office.
[May change]
Active participation in the class: 10%
Select a study topic and give a presentation on that: 10%
Write a project on that topic: 15%
Midterm: 25%
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.
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.
o The Geometry Junkyard, maintained by David Eppstein
o
Geometry in Action, maintained by David
Eppstein
o Open Problem Project: The open problems in computational geometry, maintained by Joshep O'Rourke and Erik Demaine.
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 [10%]:
Follow the guidelines below in your presentation.
o Presentation must be prepared in Beamer
o Complete your presentation within 15 minutes
o Clearly explain what the topic is
o Describe the research problems in this topic
o Application of this topic
o Related work done so far (should be recent works)
o Future work possible (as it comes to your mind and as it is mentioned in related papers)
o Direction of the project that you will do on this topic
o Selecting a good topic will also carry marks
o 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.
o You may visit "How to give a good presentation" here: http://203.208.166.84/masudhasan/good_presentation.pdf
Time: Sat 10am to 1pm
Location: Room no CSE 503
Polygon Triangulation and Polygon
Partitioning
Art gallery
theorems: Necessity and sufficiency
Triangulation
theory
Triangulation by
Ear Removal
Monotone
partitioning
Trapeziodalization
Triangulating
monotone polygons
Text: [O] 1.1,
1.2, 1.6.5-1.6.8, 2.1, 2.2. [dB] 3.3
Lecture Audio: Triangulation 1 2 3 4
Sample
questions: [pdf]
Convex Hull in 2D and 3D
Graham's scan
Output sensitive
algorithms: Gift wrapping or Jarvi's march
Lower bound of
CH
Chan's algorithm
Convex hull in
3D: Euler's formula and its consequence, gift wrapping algorithm
Text: [O] 3.3,
3.5.1, 3.6. [dB] 1.1, 4.1, 4.2.1, [Chan's paper] Section 1,
2.
Lecture audio: Convex Hull: 1 2 3
Sample
questions: [pdf]
Voronoi Diagrams and Delaunay
Triangulations:
Definition and
properties of Voronoi diagram and Delaunay triangulation
Incremental
algorithm for construction
Relation to
Nearest Neighbor graphs, MST, Largest empty circle
Medial axis and
Straight skeleton
Text: [O] 5.1, 5.2,
5.3, 5.4.1, 5.4.2, 5.5.1, 5.5.2, 5.5.3, 5.5.4, 5.6, [Incremental algorithm note],
Class Notes.
Sample
questions: [pdf]
A Voronoi
Applet: [link]
Arrangements of
straight lines in 2D
Definition and
assumption
Combinatorics of
arrangements
Zone theorem
Incremental
algorithm for computing the arrangements
Duality between
lines and points
Application of
duality: Ham-Sandwich cut, red-blue matching
Text: [O] 6.1,
6.2 (no proof for zone theorem), 6.3, 6.5, 6.7.2, 6.7.6.
Sample
questions: [pdf]
Orthogonal Range Searching:
1-dimensianl
range searching
kd-tree for 2D
Text: [dB] 5.1,
5.2
Lecture Audio: 1
Sample
questions: [pdf]
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).
Mid Term [25%]: 22-09-2012 Saturday. Syllabus: Polygon
Triangulation and Polygon Partitioning, and Convex Hull in 2D and 3D; see
detail above.
Final exam [40%]: Schedule: See notice board. Syllabus: Voronoi Diagrams and Delaunay Triangulations, Arrangements and Duality, Orthogonal Range Searching; see detail above.
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.