Computational Geometry

From ResearchWiki

Course Calendar

Course TODOs

Class Web page

• Class Web page (use this link to make alternating lecture lines). Use wordpress for styling ?
• Use Adhesive WP plugin to create a fixed "post" to simulate the front page.

Lecture notes

• Not So Short Introduction to LaTeX2e

Course Ideas

• Course should focus on techniques via exemplary problems.

• link java scripts from course web page: programming project for students to develop good animations for algorithms ?
• can students use second life to make projects ?

Projects

Project contents

• • the motivation for studying the problem
  • formalize the key geometric problems
  • survey the main methods, as well as the results
  • critical commentary on where the main bottlenecks are: what resources are important, and what are being optimized etc.
  • ideas for future directions.

• Project ideas
  • graphics themed:
    • surface reconstruction methods
    • out-of-core scene management (i/o geometry, visibility, terrains, etc)
    • ray tracing and bsps
    • collision detection (penetration depth, minkowski sums, polygonal decompositions, etc)
  • data mining themed:
    • algorithms for k-center clustering in low dimensions
    • core sets for approximate clustering
  • shapes:
    • shape matching methods, image registration
    • persistence, alpha shapes, bar codes
  • Software-based:
    • Visualization of geometric algorithms (Pat Morin's sorting applets as an example); Tim Lambert's convex hull algorithms
    • Second Life ?
  • Theory:
    • A review of methods for line (and line segment) intersection; plane sweep, topological sweep, clarkson, mulmuley, chazelle, balaban, dynamic methods ?
    • Methods for the JL transform
    • NN methods in Euclidean spaces.

Lecture Outline

Assignment Outline

1. initial assignment that covers things that should be known in advance: O() notation, basic analysis tools (sorting, median etc recurrences), greedy algorithms, divide and conquer, randomization (chernoff?), Handout: Steve Seiden's cheat sheet.
2. After convex hulls: test understanding of the techniques used: output-sensitive algorithms (n log h; dynamic convex hull ? other problems that use RIC or prune and search.
3. three
4. four

Basic Topics

Geometric Preliminaries

• Affine, linear, convex, projective geometry. Brief foray into conformal ? (meshing)

• Simplices, polytopes, polyhedra

Structures

Convex Hulls

• Optimal algorithm in any fixed dimension by Chazelle ([http://portal.acm.org/citation.cfm?id=123250