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.