Computational Geometry

• Cross-product to determine the relative orientation of two segments
• Sweep line method
  • Maintain a total preorder, and detect whether two consecutive segments intersects. (Intersect segment problem)
  • The data structure maintained: the events encountered by the sweep line
  • Trapezoidal segmentation (no line segment intersection)
  • Line segment intersection problem
• Convex Hull Problem
• Triangulation Problem
• Visibility Problem and robotics
• Planar point loction