CSE 464: Computational Geometry Sessional
April 2012 Semester
Starting from
Dr. Masud Hasan
Email: mhasan2010 "at" gmail
"dot" com
and
Mr. Sohidull Islam
Email: sohansayed@gmail.com
Lab Assignments:
Assignment 1: There are two
different implementation of Ear removal algorithm: O(n3)
and O(n2). You can implement either of them. Also remember that, you
shall have to show the output in graphics mode.
Assignment 2: While
implementing Chan’s algorithm, you shall need to implement finding the two
tangents of a convex hull of m points. If you can do that in O(log
m) time, then you will get a bonus mark. If your implementation takes O(m) time, then the running time will be affected in the
comparison, but that is ok, no penalty.
[marks]
Assignment 3: Implement the incremental construction of Voronoi Diagram (VD) and Delaunay Triangulation (DT) as
described in the class [note] and as mentioned in
[O] 5.4.2. Show VD, DT and the Delaunay Circles (DC) at the same time on the
screen. Keep options so that VD, DT or DC can be turned on/off in the display.
Instead of taking input by (x,y)
coordinates from a file, keep a mouse pointer to give input on the screen. You
will find many algorithms/applets for such construction in the Web. But be
careful of copying. Also, you shall have to implement the algorithm described
in the class and mentioned in [O] 5.4.2. An example applet: http://people.bath.ac.uk/enscjb/voronoi/tri.html
You can use any language you want and can use built-in modules for
small operations such as whether a point is inside a circle or not, which side
of a line/segment a point lies in, finding the intersection of two line
segments, taking input by a mouse pointer, etc. However, you shall have to
implement of you own the main steps of the incremental algorithm.
[marks]
Assignment 4: Implement the
easier version of Ham-Sandwich Cut problem by duality and arrangement.
[marks]
Assignment 5 (Bonus): The main task in this assignment is to learn how to use CGAL codes, not
to write own codes. Use CGAL libraries for implementing CH in 3D. In this
assignment, you shall take input some 3D points (no less than 1000) and find
their 3D CH (which is a convex polyhedron) by using the libraries/implemented
modules of CGAL. The following two things are important:
1.
Write
your own code as less as possible; the more you write your own code the less
you get marks J.
2.
You
shall have to display the input point set and the output polyhedron by some 3D
viewer, like GeomView or may be something in OpenGL.
[marks]
Quiz: See
below.
Schedule:
Monday 2:30-5pm
Location: SEL, EME building
Section A: Roll 1-60
Section B: Roll 61-Rest
7-5-2012: Assignment 1 handed out to both
Section A and B.
14-5-2012: No class
21-5-2012: Section B submit
Assignment 1, get Assignment 2.
28-5-2012: Section A submit
Assignment 1, get Assignment 2.
04-6-2012: Section B submit
Assignment 2, get Assignment 3.
11-6-2012: Section A submit
Assignment 2, get Assignment 3.
25-6-2012: Section B submit
Assignment 3, get Assignment 4.
02-7-2012: Section A submit
Assignment 3, get Assignment 4.
...
24-09-2012: Section A submit
Assignment 4.
01-10-2012: Quiz
08-10-2012: Submit (Bonus) Assignment 5 (Both
Section A and B)
Announcements:
QUIZ: 01-10-2012 (Monday). Syllabus:
Assignment 1-4. Time: 2:30pm-4:30pm, Location: CSE Room 207, 208, West Polashi.