Tension on a Graph, Part II: A Rubber Band
Python + matplotlib, 688

from pylab import*
C=cross
P,M=eval("map(array,input()),"*2)
P,N=[[P[0]]+L+[P[-1]]for L in P,M]
W=[.5]*len(P)
def T(a,c,b):
 I=[(H[0]**2,id(n),n)for n in N for H in[(C(n-a,b-a),C(n-b,c-b),C(n-c,a-c))]if(min(H)*max(H)&gt;=0)*H[1]*H[2]]
 if I:d=max(I)[2];A=T(a,c,d);B=T(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(C(c-a,b-c))]+B[1]]
 return[[]]*2
try:
 while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=P[i:i+5];P[i+2:i+3],W[i+2:i+3]=t,_=T(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=C(q-p,c-q);y=C(q-p,t[j]-q);z=C(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y&lt;=0)*(x*z&lt;0 or y*z&gt;0)*(x!=0 or d*W[k]&lt;=0)*(y!=0 or d*W[k]&gt;=0)*d
except:plot(*zip(*P))
if M:scatter(*zip(*M))
show()


Reads two lists of points from STDIN.

Example

[(0, 0), (2, -1), (3.0/2, 4.0/3), (7.0/2, 1.0/3), (11.0/2, 16.0/3), (1, 16.0/3), (0, 1), (7, -2), (3, 4), (8, 1), (3, -1), (11, 0)]
[(1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0), (6, 2), (7, 1), (6, 0)]




How it works

The key to the solution is to work in small, incremental steps.
Instead of trying to figure out what happens when we remove all the nails at once, we concentrate on the direct effects of removing just a single nail.
We can then remove the nails one by one in an arbitrary order.

Working incrementally means that we must keep track of the intermediate state of the rubber band.
Here's the tricky part: merely keeping track of which nails the band runs through is not enough.
During the process of removing nails the band can get wound and later unwound around a nail.
Therefore, when the band interacts with a nail we must keep track of how many times and in what direction it wraps around it.
We do it by assigning a value to each nail along the band like so:



Note that:


We start counting as soon as the band is tangent to the nail, even though the nail doesn't strictly affect its shape.
Recall that, unlike the illustration, our nails are dimensionless.
Therefore, if the band becomes tangent to a nail we can't tell which side of the band the nail is on by its position alone---we must keep track of where it used to be relative to the band.
We keep around nails with a value of zero, that is, nails that used to, but no longer hold the band, instead of removing them right away.
If we did, it could trigger an unwelcomed chain reaction, while we're trying to keep the effects of each step localized.
Instead, nails with a value of zero are considered eligible for removal as part of the bigger process.


Now we can describe what happens at each step:


We select a nail to remove from the band's current path.
A nail is eligible for removal if it's part of the first set of nails (save for the endpoints) or if its value is zero.
Pretending that the two neighboring nails are fixed, we figure out which nails from the second set or the pair of endpoints the band is going to run through once the selected nail is removed (we don't bother with the rest of the nails from the first set, since they'll eventually all be removed.)
We do it in a similar fashion to the solution to Part I.
All these nails are on the same side of the band, hence we assign to all of them a value of 1 or -1, depending on the side.
We update the value of the two neighboring nails to reflect the changes to the band's path (easily the trickiest part!)


This process is repeated until there are no more nails to remove:



And here's a more complicated example illustrating the band wrapping around a nail several times: