Paths in a weighted line arrangement 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.)
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.