Tension on a Graph, Part I: A Wavy String Let's plot a function f(x) = sin(πx) + 0.5 sin(3πx) over the domain [-3,3]. We can interpret this as a loose string lying on a board. Now let's drive n nails into the board at positions (x1, y1) to (xn, yn), where the xi ∈ (-3,3) and yi ∈ [-1,1]. Imagine that there are two eyelets at the end of the string, that is at positions (-3,0) and (3,0). We can now take the ends of string and pull the through the eyelets until the string is taut. This will deform our graph into a piecewise linear function.

Some pictures might help. Take 8 nails at (-2.8, -0.7), (-2.5, -0.9), (-1.2, .2), (-0.5, .8), (0.5, .4), (1.2, -0.9), (1.5, -0.6), (1.8, -0.8). The following three plots show the process described above:



For larger version: Right-click --> Open in new tab

And here is an animation of the string tightening if you have some difficulty visualising it:



The Challenge

Given a list of "nails" (which is not necessarily sorted), plot those nails and the taut string if it starts from the shape of the above function f.

You may write a program or function and take input via STDIN, ARGV or function argument. You can either display the result on the screen or save an image to a file.

If the result is rasterised, it needs to be at least 300 pixels wide and 100 pixels tall. The coordinate range from (-3,-1.1) to (3,1.1) must cover at least 75% of the horizontal and vertical extent of the image. The length scales of x and y do not have to be the same. You need to show the nails (using at least 3x3 pixels) and the string (at least 1 pixel wide). You may or may not include the axes.

Colours are your choice, but you need at least two distinguishable colours: one for the background and one for the nails and the string (those may have different colours though).

You may assume that all nails are at least 10-5 units away from f (so that you don't need to worry about floating-point inaccuracy).

This is code golf, so the shortest answer (in bytes) wins.

More Examples

Here are two more (simpler) examples:

{{-2.5, 1}, {-1.5, -1}, {-0.5, 1}, {0.5, -1}, {1.5, 1}, {2.5, -1}}




(The string coincides with the x-axis.)

{{-2.7, -0.5}, {-2.3, -0.5}, {-1.7, 0.5}, {-1.3, 0.5}, {-0.7, -0.5}, {-0.3, -0.5}, {0.5, 1}, {1.5, -1}, {2.5, 1}}




Want another Challenge?

Here is Part II!
Python + Pycairo, 727 708 608, + PyLab, 383
from pylab import*
def f(N):
 def P(u,w,N):
    T=lambda v,p:(C(v-u,p-u)&gt;0)==(C(w-v,p-v)&gt;0)==(C(u-w,p-w)&gt;0);M=[(i,n)for i,n in enumerate(N)if T(V([n[0],sin(pi*n[0])+sin(3*pi*n[0])/2]),n)]
    if M:i,n=max(M,key=lambda n:C(n[1]-u,w-u)**2);M=P(u,n,N[:i])+[n]+P(n,w,N[i+1:])
    return M
 V=array;C=cross;a=V([3,0]);plot(*zip(*([-a]+P(-a,a,map(V,sorted(N)))+[a])));N and scatter(*zip(*N));show()

Example
f([(-2.8,-0.7),(-2.5,-0.9),(-1.2,0.2),(-0.5,0.8),(0.5,0.4),(1.2,-0.9),(1.5, -0.6),(1.8, -0.8)])


How it works

 Suppose we know that the taut string passes through two points A and
 B (we can always start with  A = (-3, 0) and B = (3, 0).) As we pull the string, it &quot;wants&quot; to take the shortest path possible between
 A and B, that is, ideally, the segment AB. However, if there are any nails in the area bounded by the function (sin πx + ...)
 and AB, then at least one of them must block the string. In
 particular, the nail(s) farthest away from AB within the said area
 must block the string. Hence, if C is this nail, we know that the
 taut string must pass through C, in addition to A and B. We can
 now repeat the process for the segments AC and CB, and continue in
 this fashion until eventually there are no more intervening nails.
 
  
 This is a binary divide-and-conquer algorithm with a linear scan in
 each step, so it has a best-case complexity of O(n log n) and
 worst-case complexity of O(n2).