计算几何

1.Convex Hull

def by princeton:

Given set of N points in the Euclidean plane, find minimum area convex region that contains every point.

Intuition: points are nails perpendicular to plane, stretch an elastic rubber bound around all points; it will minimize length.

there are some beneficial trials, like extreme points(which is O(n^4)), extreme edges(which is O(n^3)), because in these trials we have to wrap up some useful functions like To_Left, which is also used in better algorithms.

Applications. Among oldest and most well-studied problems in computational geometry problems.

• Robot motion planning.
• Shortest perimeter fence enclosing P.
• Smallest area polygon enclosing P.
• Unique convex polygon whose vertices are points in P that encloses P.
• Smallest convex set containing all N points (i.e., intersection of all convex sets containing the N points).