24-384A  Computational Geometry  Fall'97

-- Special Topics in Design -- Mechanical Engineering  Carnegie Mellon University

  Place: 206 Scaife Hall  Time: Tue&Thu 9:00-10:20am  Instructor: Kenji Shimada 

---

 Announcements

 
• <12/14> Project home pages:

Programming projects
• Polygon Partitioning: Monotone Triangulation (Bader Al-Essa)
• Rotation of General Triangle in a 3-D Space (Andrew Flores)
• Drawing Brick Walls In VRML (Eric Paulsen)
• Surface Generation from Spatial Wireframes (Jonathan Pompa)
Survey projects:
• Generating Optimal Computational Grids: Overview and Review (Taek Choi)
• Minimizing Waste in Manufacturing (Layout) (Young Rak Kim)
• <12/14> Some pictures from project home pages
   

With rapid advances in computer hardware and graphics systems, handling three dimensional geometric information on the computer has become essential in many research and application areas, such as computer-aided design (CAD), computer-aided manufacturing (CAM), computer-aided engineering (CAE), robotics, computer vision, and computer graphics.  This course teaches basic concepts and algorithms to solve common geometric problems in these application areas.  Such geometric problems include: (1) line segment intersection, (2) polygon inclusion, (3) convex hull calculation, (4) range searching, (5) closest-point search, (6) domain tessellation, (7) curve fitting, (8) collision detection, (9) geometric feature search, and (10) optimal packing.  The course is designed to give students an ability to design and implement solutions to these geometric problems.

Instructor

• Instructor: Kenji Shimada
Office: 318 Scaife Hall
Email: shimada@cmu.edu
Phone: 8-3614
Office Hours: Tue 10:30-11:30, or by email appointment

• For past handouts contact: Ms. Candace Bair
Office: 209 Scaife Hall
Email: bair+@andrew.cmu.edu
Phone: 8-2508

• Basic linear algebra and calculus
• Some programming experience in at least one language (C, C++, Java, Mathematica, Basic, Fortran, etc.)

The subject matter to be presented in this course may roughly be divided into 10 categories.  These categories and the approximate time to be devoted to each are:

• Introduction (1.5 wk)
• Vectors, Matrices, Coordinate Transformations
• Points, Lines, Polygons
• Programming (1.5 wk)
• Data Types, Input/Output
• Data Structures, Arrays, Linked Lists, Stacks, Queues, Trees
• VRML, OpenGL
• Global Property Calculation (0.5 wk)
• Area, Volume
• Analysis of Algorithms (0.5 wk)
• Time Complexity, Space Complexity
• Elementary Sorting and Searching (1 wk)
• Selection Sort, Insertion Sort, Quicksort, Mergesort
• Sequential Search, Binary Search, Binary Tree Search, Hashing
• Intersection (1 wk)
• Line Segment Intersection, Polygon Inclusion, Boolean Set Op.
• Convex Hull (1.5 wk)
• Package-Wrapping, The Graham Scan, Interior Elimination
• Range Search (1 wk)
• Grid Method, kD-Tree
• Triangulation (2 wk)
• Polygon Triangulation, Delaunay Triangulation, Voronoi Diagrams
• Engineering Applications (2 wk)
• Project Presentation (1 wk)

There will be no specific textbook. Reading materials will be provided by the instructor from reference books and technical papers.

Assignments

Six problem sets, some with hands-on programming, are given to help students better understand the course material. The programming part of the assignments is not too intensive, and the introduction to necessary programming environments and software tools is provided by the instructor. Reading materials are occasionally given from book chapters, technical journals and conference papers.

The solutions to the Problem sets that you hand in should be generated by your individual effort.  It is ok to discuss the problems with other students, but the written solutions and programs must be your own work and not copied from someone else.

Hand in your solutions to the problem sets at the beginning of the class (9:00am) on the due date.

Late policy:  15% off for one CMU class day, 30% off for two CMU class days, 50% off for three CMU class days, and 90% off afterward.  For example, suppose the due date is 9:00am Thursday morning, you will lose 15% if you hand it in by 9:00am Friday, 30% by 9:00am next Monday, 50% by 9:00am next Tuesday, and 90% afterward.

Pictures from the Problem Sets
 

• PS5: Convex Hulls

 

data30

data100

data500

• PS4: Polygon Triangulation

data1

data2

data3

 

Time management is a critical factor to your academic success, as to any professional environment.  Being a 9 unit course it is expected that each student will devote at least 9 hours a week in completing: (1) assigned reading, (2) attending lectures, (3) problem sets, (4) reviewing lecture materials, and (5) preparation for quizzes.  While the exact time devoted by individuals would vary depending on the background, a suggested time budget follows:

The final grade will be determined by an absolute method of grading.  This is to allow you to obtain a grade based on your individual performance without having to compete with each other.  It is thus possible for the whole class to get an A grade or in the other case for the whole class to get a C grade.  (Of course we hope that you all will work hard and get an A :-)  The evaluation of your work in the course will consist of the following items:

How am I doing with Problem Sets and Quizzes?
 

• <12/14> Project: Average score 70.5/80.0
• <11/25> Quiz 2: Average score 82.7/100.0

Q2-1	Q2-2	Q2-3	Q2-4	Q2-5	Total
6.0	11.5	16.8	26.2	22.7	82.7

• <11/10> Problem Set 5: Average score = 50.0/50.0, good job!
• <10/28> Problem Set 4: Average score = 38.3/40.0
• <10/19> Midterm grade is based on PS1, PS2, PS3, Quiz1, and class participation: Average score = 154.5/ 200.0
 

PS1	PS2	PS3	Quiz1	Class  Participation	Total
25.0	32.7	20.8	48.0	28.0	154.5

 
•  <10/19> Quiz 1: Average score = 48.0/60.0

Q1-1	Q1-2	Q1-3	Q1-4	Q1-5	Q1-6	Total
8.5	5.7	8.0	9.7	8.2	8.0	48.0

 
• <10/19> Problem Set 3: Average score = 20.8/30.0

PS3-1	PS3-2	PS3-3	Total
5.7	6.8	8.3	20.8

•  <9/24> Problem Set 2: Average score = 32.7/50.0

 

PS2-1	PS2-2	PS2-3	PS2-4	PS2-5	Total
7.8	6.3	6.3	5.5	6.7	32.7

 

• <9/14> Problem Set 1: Average score = 25.0/30.0

The following is the tentative description of the project that you will do toward the end of this course.  The due dates and the mission statement are subject to change.

• Schedule
• 11/11 (Tue) One page project proposal due
• 12/2 (Tue) Project Report due
• 12/2 (Tue) and 12/4 (Thr) Project Presentation
• The project will count 20% of the total grade. So, please "design" the difficulty and coverage of your project so that you will spend the time and effort that you would spend for two Problem Sets.
• You can do either a "Survey Project" or a "Programming Project."
• In a Survey Project, you are asked to find at least 3 technical papers on your topic from conference proceedings and technical journals. Read these papers, summarize problems, categorize previously proposed approaches, discuss the pros and cons of each approach, give discussion and observation. and wrap up with future directions that you think might be promising.
• In a Programming Project, you are asked to define a problem (just like in a Problem Set), write a code, show the results with several test cases, and wrap up with discussion and observation. Define your programming task so that the difficulty and the coverage of your project is appropriate, that is, approximately two times more difficult than programming assignments in Problem Sets.
• How you proceed:
• Step 1: Find a topic related to computational geometry that you are interested in.
• Step 2: Choose the type of your project, Survey Project or Programming Project.
• Step 3: Write and hand in a one page project proposal (Due: 11/11/97). This is to give me a chance to give you feedback on your topic if it seems too easy or too tough. (You can later change the description of the proposal with my permission.) Include the following items in your proposal.
• Your name
• Project Title
• Project Type: "Survey" or "Programming"
• Mission Statement: Describe the goal and coverage of your project.
• Background information: Explain why you are interested in this problem. Also give some background, for example, if this is a part of your senior project, MS project, or Ph.D. project.
• Step 4: Work hard for a couple of weeks :-)
• Step 5: Write a Project Report as a html document and hand it in as the following afs file (Due: 12/2/97):

/afs/andrew/cit/meche/cie01/cg97/your_name/project/index.html
You can use as many html or wrl files as you like in your project directory, if they are linked from your index.html file. The format of the report is open, but your report should include the following information:
• Survey Project: problem summary, classification of previous approaches, discussion of pros and cons of each approach, discussion and observation, and a list of the references. Also hand in one copy of all the reference papers.
• Programming Project: problem summary, description of your algorithms, results of some test cases, and discussion and observation. Hand in your source code in the following directory:

/afs/andrew/cit/meche/cie01/cg97/your_name/project/code/
• Step 6: Project Presentation: 12/2/97 (Tue) and 12/4/97 (Thr). Each student will give a 20min. presentation about his/her project. The order of the presentations will be decided on the first day, so everyone should prepare their presentation material by 12/2/97.

• <11/1> Quiz 2 is scheduled on 11/18 (Teusday)

        lecture coverage:  10/ 16-11/13
        problem set coverage: PS4 -- PS5
        Approximately 1/3 of Quiz 2 will be from Professor Choset's lectures.
• <11/1> The following three data files for Problem Set 5 are ready:

     data30 (data30.wrl), data100 (data100.wrl), and data500 (data500.wrl).
They can also be found at: class_afs/code/chull/data.  Study data30.wrl, data100.wrl, and data500.wrl to see how to draw a set of points in VRML files.
 

data30

data100

data500

 
• <11/1> Project proposal is due 11/11.
• <11/1> Please print out class_afs/CGreport.ps.  This document will be useful if you are going to do a survey project.
• <10/28> Problem Set 4: Average score = 38.3/40.0
• <10/28> Problem Set 4: Polygon triangulation results
 

data1

data2

data3

 
•   <10/19> Midterm grade is based on PS1, PS2, PS3, Quiz1, and class participation: Average score = 154.5/ 200.0
 

PS1	PS2	PS3	Quiz1	Class  Participation	Total
25.0	32.7	20.8	48.0	28.0	154.5

 
• <10/19> Problem Set 3: Average score = 20.8/30.0
 

PS3-1	PS3-2	PS3-3	Total
5.7	6.8	8.3	20.8

 
•  <10/7> No class on 10/14.  A special office hour for PS4: 10/14 9:00-10:20 @ B130 Hamershlog Hall.
• <9/27> Quiz 1 is scheduled on 10/9 (Thursday)
• lecture coverage:  8/26 -- 10/7
• problem set coverage: PS1 -- PS3
• <9/24> Problem Set 2: Average score = 32.7/50.0
 

PS2-1	PS2-2	PS2-3	PS2-4	PS2-5	Total
7.8	6.3	6.3	5.5	6.7	32.7

 
 
• <9/14> Problem Set 1: Average score = 25.0/30.0
 

PS1-1	PS1-2	PS1-3	Total
9.8	10.0	5.3	25.0

 
•  <9/14> I had an error in one of the handouts from Thursday's class (9/11). In "HOW TO USE MAKEFILE," the distance that the program should return is distance = 24.313342 instead of 9.460444. Thanks Taek for letting me know about this.
• <9/7> Hand-in directories for Problem Set 1 are located at

/afs/andrew/cit/meche/cie01/cg97/students/your_first_name/ps1.
• <8/26> For viewing VRML files, use VRweb for virtually all platforms or NetscapeNavigator+Live3D for Windows95/NT.
• Download: VRweb for popular unix platforms (SGI IRIX, Sun Solaris, Sun OS, DEC Alpha, DEC ULTRIX, HP-UX, IBM AIX, LINUX, FreeBSD) or VRweb for Windows95/NT.
• <8/26> VRML V1.0 Specification
• <8/20> This new course is an introduction to computational geometry in fall 97 for undergraduate students in engineering.