Messed-up late night thoughts

[ilai]

I had trouble sleeping last night, because my mind drifted off to a problem, which I record below. I make no guarantees with respect to coherence :)

Say that you have a set of tuples (p, u, v), where p is a point on the x-y plane, u and v are positive integers, and u > v. One of the tuples is the origin tuple, (p₀, u₀, v₀), and no two tuples share the same point.

A run is a nonrepeating sequence of n such tuples (p_i, u_i, v_i), starting with the origin tuple, where any sum u₀ + v₁ + v₂ ... + v_i is at least u_i+1.

Let's say the length of the run is the sum of all the distances between adjacent p_i and p_i+1 points in the sequence, and the size of the run is the sum u₀ + v₁ + v₂ ... + v_n.

Now I want to do one of the following things:

• Find a run with maximum size that is no more than a certain length
  
• Find a run with minimum length that has at least a certain size
  
• Say that there's a certain subset of tuples; find a run that is no more than a certain length, but contains the maximum number of tuples in said subset
  

Or maybe I want to complicate the problem:

In-between tuple restrictions:

• Impose the restriction that in a run, a point p_j cannot be collinear and between two points later in the run, p_i and p_i+1
  
• Impose another restriction that the third point cannot be m distance away from the line segment between p_i and p_i+1, where m is some multiple of the cube root of the length of the run up to the tuple with point p_i.
  

Turning penalty:

• For each three adjacent tuples, add to the length some penalty amount proportional to the smaller angle created by the rays (p_i, p_i+1) and (p_i+1 , p_i+2)
  
• Or make the penalty proprotional to the absolute value of the sine of the angle, plus a little extra if the angle is greater than pi/2
  

Then my head went "BA-NA-NA" and I decided I should forget about this and go to bed. Maybe I'm mad.

Comments

[staticentropy.livejournal.com]

Your problem seems to be a pretty standard dynamic programming problem. I can explain the algorithm in more detail elsewhere or in person; LJ comments are certainly not the way.

I'll see if I can implement the versions without any restrictions and make it understandable, to boot. Or you can find me in person sometime.

[ilai]

I corrected my typo, so I don't know if that changes things a bit. I must admit I haven't thought any solution very hard (or at all, given the time of night this came to mind :-)

I know dynamic programming is pretty standard for this kind of problem if I were to be optimizing one quantity--but given the various other constraints (e.g. must no more than a certain length, and lengths don't have to be integral here), would it still work? Have to remember my 6.046 now....

[staticentropy.livejournal.com]

Hm. Actually, I might have misunderstood the problem. I'm still sure there is a fairly simple solution to it - it's probably more of a graph theory problem (but, of course, the standard algorithms use DP to speed things up). I'll think about it some more.