Minimizing Piece-wise Linear Area for Solution to Convex Hull of Segments

In a previous post we saw a solution to the parallel line segment smallest convex hull problem. See the post and familiarize yourself with the solution. You will see that the last paragraph explains how to find the optimal point p that minimizes the area between the point, two polylines, and the tangent lines between p and the polylines.


There we want to determine the point p in segment sl such that the area A(p) is minimized. See this figure.


See that the straight lines defined by the extension of the sides of the polyline (top or bottom chain) that are reachable from p by drawing a line that does not cut the polyline intersect the segment sl.


Extend the sides of one of the polylines (top or bottom chain). If the side is reachable from any point in  sl by drawing the point to the side without cutting the chain, then the extension into infinite of the line defined by that side intersects the segment  sl . To find the optimal p to minimize A(p), we just need to consider all the above mentioned intersection points.


Let x1, x2, ..., xa be the points of intersection from the extension of the lines sides of the top chain and segment sl, ordered from top to bottom.


Let y1, y2, ..., yb be the points of intersection from the extension of the lines sides of the top chain and segment sl, ordered from top to bottom.


We just need to consider all the intersections between two intervals [xi,x i+1] and [yj,y j+1] for all i and j possible, which quantity that is is linear in the number of segments from the problem solved in the last post. See this figure for a visual.


Then see this figure and realize that for each of those intervals, realize that the optimal point p for that interval will lie in one of the extreme points of the interval, or else then any point in the interval will give you the same area A(p). The reason is that the chains form a monotone convex polyline, and whichever of the two points al(p) and bl(p), as shown in the figure, is closest from sl will determine the point p in sl that minimizes A(p).