Paths in a weighted line arrangement

Question

This is a followup to my followup to David's question. This question admittedly leaves the original motivation far behind, but it might provide some useful intuition.

Suppose we are given a set of n non-vertical lines, each with a (possibly negative) real weight. The lines partition the planes into convex polygonal cells; the cell complex is usually called an arrangement. Define the weight of a cell to be the sum of the weights of the lines that lie above it. Let p be a point that lies above every line, and let q be a point that lies below every line.

Suppose there is a path between p and q that intersects only cells with non-negative weight. Is there a path from p and q that intersects only cells with non-negative weight and crosses each line exactly once?

Equivalently: Suppose we are given a set of points in the plane, each with a (possibly negative) real weight. Now imagine continuously moving a straight line, starting above all the points and ending below all the points, such that the line is never vertical. Call the motion legal if at all times, the total weight of the points above the line is non-negative.

If there is a legal motion, must there be a legal motion where the moving line passes over each point exactly once?

(It is easy to find such a path/motion or determine that none exists in $O(n^2)$ time.)

Answer 1

The answer is no, me think.

To see why consider two lines that are a perturb copy of each other that intersect at a point p. By giving one line weight 1, and one line weight -1, we created a tiny wedge where the path can not go through. Think about this wedge now as a ray. Now, using a collection of such rays, we can create the following configuration:

------------------------

             -----------------------------------

-------------------------

             --------------------------------

--------------------------

That is - interleaving horizontal rays. Now, the path must wiggle between these rays in the natural way. It is now trivial to add an almost vertical ray that its tail (i.e., non ray part) intersect all the horizontal rays. The path must intersect the two lines defining this ray as many times as we want.
Here is a figure:

_{(source: uiuc.edu)}

(Ipe source.)
The solution is slightly more complicated because these rays open up. By adding the two rays on the sides, one guarentees that only the region of interest is really relevant.

Answer 2

If there is a legal motion, must there be a legal motion where the moving line passes over each point exactly once?

I think the answer is No.

Consider the following points (co-ordinates written in the parantheses) - A(1, 1), B(0, 0), C(-1, -1) and D(-2, 0). Let them have the following weights -

A: +10 B: -100 C: +500 D: -5

Let's describe the current position of the line by specifying the set of points lying above it. Initially, the line is above all the points. Next, the only option for it is to cross A and reach the position {A}. It cannot cross B now because of its very large negatice weight, so the only option is to cross D and reach the position {A, D}. It can still not cross B. However, if it rotates a bit, gets C above it, pushes A below and reaches the state {C, D}, then it will have a very large positive weight above it and so in the next two steps it will be able to cross B and then A and hence reach below all the points.

Therefore even though there is a legal motion, there is none where the line crosses each point exactly once.

Here's a legal motion for the above set of points. Different positions of the line have been marked with numbers increasing in the chronological order. The initial position is not shown, but you can imagine it to be somewhere above all the points.