Triangulation

• Use Graham’s scan to derive the triangulation. Keep track of all the intermediate triangles.
• Maximize the minimum angles in the triangles to achieve minimum math error.
• Delauney triangulation
• Voronoi Diagram
  • Bipartite lines
  • Calculate intersection of the half planes
• Post office problem, calculate bisector between a post office and all the other offices. — $O(n^2)$ time