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.

[ilai]

Sorry, I made a typo in the definition of a run--I meant to say "at least u_i+1", not "at least v_i+1". *edits*

[luckylefty.livejournal.com]

Oddly enough, this exact problem has been keeping me up late at night, too. Though I've been working out solutions to specific instances of the problem, rather than trying to find a theoretical general solution.

[ilai]

Yay, I'm not the only one! :-)