Meeting 1: Course Introduction

Introductions:  Lecturer, LA (Lab Assistant), Students

• What do we do?
• Why are we here?

• Geometric representations and data structures
• Algorithms to construct such data structures
• Queries defined on geometric data structures
• Visual inspection and interaction techniques
• High-level applications of all of the above

  Stuff you can use !

Biases:

• Interactive (not batch) computations
• Approximation for responsiveness
• Convergence to analytic solution if possible
• Robust, self-checking algorithms
• Data-dependent coordinate systems
• Importance of visual inspection, manipulation
• "If it looks wrong, it probably is wrong"
• "If it is wrong, how can we find out?"

• M. de Berg et al., Comp. Geometry: Algorithms and Applications
• Selected readings from papers, course notes, web, et cetera.

• Textbooks:
• J. O'Rourke, Computational Geometry in C
• M Laszlo, Comp. Geometry and Computer Graphics in C++
• F. Preparata and M. Shamos, Computational Geometry
• Edelsbrunner, Algorithms in Combinatorial Geometry
• M. Goodrich and R. Tamassia, Data Structures and Algs in Java
• Applications:
• M. Lin and D. Manocha, Eds., Applied Computational Geometry
• J. Blinn, A Trip Down the Graphics Pipeline
• Mathematics:
• J. Oprea, Differential Geometry and its Applications (w/ Maple)
• L. Santalo, Integral Geometry and Geometric Probability
• PhD Theses:
• M. de Berg, Efficient Ray Shooting and Hidden Surface Removal
• J. Stolfi, Primitives for Computational Geometry
• Utilities:
• W. Beyer, Ed., CRC Standard Mathematical ... Formulae
• OpenGL documentation and examples (most online as well)

• Course Introduction
• Goals, philosophy
• Overview of material we will cover
• Segues between bodies of material
• Repository for collected/generated code nuggets
• We have "seeded" it with lots of good stuff
• Guided presentations, one per student per meeting
• Two weeks of preparation recommended
• Presentation (typically HTML) of suggested concepts
• Interactive demonstration of suggested concepts
• Pointers to working code for substrate, interaction
• Suggested discussion/exploration topics
• Meeting with course staff one week beforehand
• Short programming exercises (few hours per week)
• Exploratory coding, visual demonstrations
• Infrastructure, many examples provided
• Also -- five minute "demo breaks" in class
• Course project (ordinarily, two-student team)
• Proposal (1W), feedback (1W), development (1M)
• Presented to class at end of term
• Course summary

• Class participation
• Individual presentation
• Exercises, creativity, enthusiasm
• Project and presentation

Example interactions (partial list):

• geometer (2D "theorem proving" environment)
• voronoi (interaction; voronoi; delaunay; convex hulls; reductions)
• openglCDT (2D constrained delaunay triangulation)
• gur (princeton radiosity, source/  intervisibility)
• plucker (lines in 3D, constrained line selection)
• roam (3D navigation, visibility, inspection)
• demokin ("kinetic" computational geometry)

Previous Meeting .... Next Meeting ... Course Page

Last modified: Feb 1998