CS 497 JE, Spring 2000

Computational Geometry

TuTh 11:00-12:15, 159 Altgeld Hall
Instructor: Jeff Erickson

Computational geometry is the field of theoretical computer science devoted to the design, analysis, and implementation of algorithms and data structures to solve geometric problems. These problems arise in several different areas, including computer graphics, robotics, databases, data mining, parallel computing, statistics, and pure math. Their solutions combine traditional algorithmic techniques with beautiful results from combinatorics, geometry, and other mathematical areas. Computational geometry was the breeding ground for several important techniques that later spread to the broader algorithms community - for example, dynamic data structures, randomized algorithms, and external memory computing - and continues to be one of the most active, interesting, and applicable areas of algorithms research today.


The exact topics will depend on the interests of the participants, but here is a sample of possibilities. Please let me know if there's something specific you want to talk about!

  • Polygons
  • Convex polytopes
  • Triangulations
  • Voronoi diagrams
  • Convex decompositions
  • Arrangements
  • Visibility graphs
  • Problems:
  • Convex hulls
  • Nearest neighbors
  • Point location
  • Range searching
  • LP-type problems
  • Intersection
  • Lower bounds
  • Techniques/Paradigms:
  • Sweep
  • Divide and conquer
  • Prune and search
  • Random sampling
  • Dynamization
  • Kinetic data structures
  • Perturbation
  • Applications:
  • Mesh generation
  • Simplification
  • Reconstruction
  • Motion planning
  • Collision detection
  • Hidden surface removal
  • Clustering
  • Administrivia

    Some useful web pages:

    I talk in pictures not in words.
    - Peter Gabriel
    "...And Through the Wire"
    Peter Gabriel III (Melt) (1980)

    I have no arguments to offer, my figures are my proofs.
    Laugh away these truths and facts if you can.

    - Theodore Heisel
    The Circle Squared Beyond Refutation (1934)

    Automatic polygon meter
    Analog toy computer item
    Triangulate me, moot copy
    Goatee community portal
    Oatmeal recomputing toy
    Optional gutter may come
    Typical rommmate tongue
    Get your calm emotion, Pat.
    Get your campmate lotion
    Immature galoot potency
    A triplet comet among you
    Cut lame emotion - go party!
    Operate coital Tommy-gun
    Copulate my rotation gem.
    Young male potato metric
    Go try tapioca emolument
    Ugly poetic monotremata
    Magical poem torn out yet
    Automatic mangle poetry

    CS 497 (Spring 2000) - Jeff Erickson (jeffe@cs.uiuc.edu) 09 Jan 2000