CSE 463: Computational Geometry

April 2012 Semester

Starting from May 07, 2012

Course teacher:

Dr. Masud Hasan

Associate Professor

Department of CSE, BUET

Office: West Polashi 117

Phone: PABX: 8614640-44, 9665650-80, Ext. 6113

Email: mhasan2010 "at" gmail "dot" com

Books:

1. [O] Computational Geometry in C, by Joseph O'Rourke, Second Edition, Cambridge University Press, 1998

2. [dB] Computational Geometry, by de Berg, van Kreveld, Overmars, and Cheong, Third Edition, Springer, 2008

3. Other materials/references will be supplied as required

Schedule:

Time: 8-9 Su M T

Location: CSE 207

Course syllabus (will gradually grow and be updated):

All related exercises are by default added

Introduction:

Course information

Course policies

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] [Triangulation-2] [Triangulation-3] [Triangulation-4] [Triangulation-5]

Sample questions: [pdf]

Class Test 1

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] [Convex-hull-2] [Convex-hull-3] [Convex-hull-4] [Convex-hull-5-Voronoi-1]

Sample questions: [pdf]

Class Test 2:

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.

Lecture Audio: [Convex-hull-5-Voronoi-1] [Voronoi-2] [Voronoi-3] [Voronoi-4] [Voronoi-5]

Sample questions: [pdf]

A Voronoi Applet: [link]

Class Test 3 [Solution] [Marks]

Arrangements and Duality:

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.

Lecture Audio: [Arrangements-1] [Arrangements-2] [Duality-1] [Duality-2]

Sample questions: [pdf]

Class Test 4 [Marks] [Marking Scheme]

Line Segment Intersection

Intersection of Segments

Overlap of two polygons---convex and non convex polygon

Text [O] 7.7, 7.8

Lecture Audio: [Segment-1] [Segment-2]

Sample questions: [pdf]

Graph Drawing

Class Test 5 [Marks]

Orthogonal Range Searching

Motivation from DataBase

1d

2d

Text [dB] 5.1, 5.2

Lecture Audio: [Range-1] [Range-2]

Sample questions: [pdf]

Announcements:

- Class Test 1: 20-5-2012 Sunday, in class. Syllabus: Polygon Triangulation and Polygon Partitioning.

- Class Test 2: 03-6-2012 Sunday, in class. Syllabus: Convex hull; see detail above.

- Class Test 3: First class after the Mid-term vacation (24-06-2012, Sunday). Syllabus: Voronoi Diagram and Delaunay Triangulation; see detail above.

- Class Test 4: 10-7-2012 Tuesday, in class. Syllabus: Arrangements and duality; see detail above.