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.)