This problem is convex hull in disguise.
The “does not intersect the object” requirement of a base line is really a convex hull problem. Here is a reference solution.
