Fundamental Algorithms:

Some Important Results:

Euler and Poincare Formula:

        Perhaps the most elegant result in geometry. The Euler's formula relates Vertices (V), Edges(E) and Face(F)
                                                             

        This formula was further extended by Poincare  for polygons having holes.
                                    
                                                                                                                  

        There are two great implications of these formula.

        1.    By justing counting vertices, edges and face, we can detemine number of holes in the surface. 
        2.    There are only five regular polyhedra. ( it can proved using Euler's formula),                                  

The Four-Color Problem:

        The problem was posed in 1852 and perhaps the its correct proof was the most daunting. It states that:

• Four colors are sufficient to color any regions sharing a common boundaries such that adjacent colors of the regions are different.
• Every planar graph can be five colored. 
• Any map on the torus require at the most seven different color.
  

Art Gallery Problems:

Theorem I :  Given a polygonal art gallery with "n" vertices, are always sufficient and occassionally necessaru to guard
                     the gallery.
Theorem 2:  Any rectangular art gallery with "n" rooms needs exactly
Theorem 3:  Given a polygonal art gallery with "n" vertices and "h" holes, guards are always sufficient and
                     are occassionally needed.

Sphere Packing:

        Newton conjectured that twelve spheres can be compactly packed so that every sphere touch the
        central sphere. Many believed that the number was 13, but it was finally proved in 1992 in favour of
        Newton.

                  

Uniqueness of Delaunay Triangulation:

NP Completeness of Tetrahedrazibility:

Every 2D simple polygon has valid triangulation. In 3D, polygon tetrahedraziblity is NP complete problem.

Applications:

• Robot motion planning.
• Spectral Surface Reconstruction with Noisy Point Clouds.
• All Hex and All-Quad Meshing methods.
  
• Surface Smoothing Algorithms.
• Collision Detection.
• Art Gallery Problems (or Sensor Placement Algorithms)
• Topological Simplifications.
• VLSI Floor Design Optimization.