Halfplanes and Duality

convexhulls.md

:uid: convexhulls :title: Convex Hulls :description: Halfplanes and Duality :tooltip: None :tag: :group: :license: CC-BY-4.0 :source: https://api.github.com/gists/5a8a82654acd8139af13

An introduction!

Convexity of a Point Set

Consider a set P of points on the plane. The convex hull, $conv(P)$, is the smallest convex set that contains P. An intuitive way to visualize this is to imagine placing a loop of string around all the points, and then pull it as tight as it will go. The example below shows a set of points along with their convex hull. You can drag the points around and see how the convex hull changes as the point set is adjusted.

<iframe src="/3pt/minimal/CounterPoint/minimals/CHull.html" style="width:100%;height:450px;border:none"></iframe>

While we don't explore them in this blog post, there are many different algorithms for computing the convex hull.

Instead, let's explore a related, but different problem.

The Halfplane Intersection Problem.

Halfplanes

Consider a line within the plane. This line divides the plane into two halves, known as halfplanes. In the example below, the red line cuts the plane in half, and one of the halfplanes is shaded in red. You can drag and rotate the line using the larger and smaller nodes, respectively.

<iframe src="/3pt/minimal/CounterPoint/minimals/Halfplane.html" style="width:100%;height:450px;border:none"></iframe>

Halfplane Intersection

The shared region of two or more halfplanes is known as a halfplane intersection. In the example below, we have a red halfplane defined by the red line, and a blue halfplane defined by the blue line. The halfplane intersection shows up as the purple shaded region. Again, you can drag around the lines to see how the halfplanes intersect.

<iframe src="/3pt/minimal/CounterPoint/minimals/Halfplane.html" style="width:100%;height:450px;border:none"></iframe>

Upper and Lower Envelope

A slight variant on the Halfplane Intersection problem is the Upper and Lower Envelopes of a set of lines. Consider a set of lines, each dividing the plane into two halfplanes. For each line, we consider the upper halfplane to be the halfplane 'above' the line, and the lower halfplane to be the one 'below' the line. The region above (below) the line refers to the space where, if you shoot a ray starting from any point within the region straight upward (downward), you never intersect the line.

Then, the upper envelope is defined as the intersection of the set of upper halfplanes, and similarly the lower envelope is the intersection of the lower halfplanes.

<iframe src="/3pt/minimal/CounterPoint/minimals/Envelopes.html" style="width:100%;height:450px;border:none"></iframe>

Line Point Duality

You may be asking, what do all these lines and halfplanes and envelopes have to do with points and convex hulls? To answer this, we have to look at Line-Point Duality.

Duality

Consider a point p = (a,b) where a and b are the x and y coordinate of the point. The 'dual' of this point is obtained by mapping p to the function of a line p*=ax-b, where a corresponds to the slope of the line, and b the y-intercept.

To see this concept of duality in action, play around with the points and lines below. Try aligning a bunch of points to be collinear. What happens to the lines?

<iframe src="/3pt/minimal/CounterPoint/minimals/DataView.html" style="width:100%;height:450px;border:none"></iframe>

Convex Hulls and Envelopes

By applying line point duality to a set of points, we get an interesting result, as described in the lemma below.

Lemma: Let P be a set of points in the plane. The counterclockwise order of the points along the upper (lower) convex hull of P is equal to the left-to-right order of the sequence of lines on the lower (upper) envelope of the dual P* (Citation: David M Mount Notes2012, CMSC754)

A more in depth proof can be found (by expanding this section of the awesome scalable document)

To see this in action, play around with the example below. Each point and it's dual line are the same color. The upper convex hull and lower envelopes are shown in silver, and the lower hull and upper envelope are gold.

<iframe src="/3pt/minimal/CounterPoint/minimals/CHullLandUWithLineDuals.html" style="width:100%;height:450px;border:none"></iframe>