Computation Geometry

  • Object:
    • point:(x,y)
    line, segment, array:(p,q)
    polygon:P0, P1, P2, ..., PN, P0
    planar subdivision
  • Questions:
    • intersection
    point-location static/dynamic
    decomposition
  • Applitions:
  • Graphics
  • CAD
  • VLSI
  • Image Processing
  • Pattern Recoginition
  • Robotics
  • Paradigms:
  • Incremental Construction
  • Plane Sweep
  • Locus
  • Divide & Conquer
  • Geometric Transformation
  • Prune & Search
  • Dynamization