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).

Parallel Line Segments Smallest Convex Hull

Here I am gonna write on what I learned about finding the smallest convex hull (smallest CH) of a set of parallel line segments from reading Loffler and Kreveld's work.


Here is the problem:
Given a set of parallel (vertical) line segments, choose a point on each line segment such that the area of the convex hull of the resulting point set is the smallest possible among all possible selections of this point set.


See this figure for a visual.


To solve this problem we are first to see the following definition:


Greatest Common Region (GCR): The greatest common region of a set of line segments S is the largest region that is part of the convex hull of every possible choice of points on the segments.


Now let's see the definition, in this context, of top and bottom chain of a set S of parallel vertical line segments.


top chain (resp. bottom chain) of S: Polyline that contains no lower (resp. higher) endpoints of any segment over (resp. under) it.


After seeing these definitions, go ahead and realize that the region enclosed between the top and the bottom chain of S forms the greatest common region (GCR) of the set S of parallel vertical line segments.


Also realize that the area (A(GCR)) of the GCR of S is equals to zero if and only if the area (A(C*)) of the optimal (aka smallest) convex hull of S is zero.
It is easy to check if A(GCR) == 0 in linear time. // O(n)
If it is found that A(GCR) == 0  then obviously the optimal solution for smallest convex hull of S has area zero.


Hence just assume that A(GCR) > 0. :)


Let sl and sr be the leftmost and rightmost segments of the set S.


Let p be a point in  sl and a point q on  sr, then let al(p) th rightmost point in the top chain such that the line from p to al(p) does not intersect the top chain. Define bl(p) respectively with the bottom chain. Also define ar(q) and br(q) respectively for q.
See figure 2 inside this picture for a visual.


Now you can go ahead and realize that for a certain p and q in the right leftmost and right most respectively segments, then the area enclosed by the chain
p -> al(p) -> ar(p) -> q -> br(q) -> bl(q) -> p
is the optimal solution. The challenge is then to find the right p and q.


To find the right p just go ahead and do:
For each pair of edges e1 and e2 of the top and bottom chain respectively whose projection onto infinity intersect sl at points y1 and y2 respectively, go ahead and pick the optimal point x1 for the interval in sl between y1 and y2. Do the same for q and pick a point x2 respectively. Find the area enclosed in in O(log n) time. Pick the smallest of all the solutions and return.


The problem can therefore be solved in O(n log n) time.

Largest Diameter of indecisive points

Being a long time since last post:
Largest Diameter of square regions of indecisive points