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

• Just some clarification: Are these lines in a Cartesian plane? Do they have (x,y) endpoints? – Daniel Apon Sep 21 '10 at 16:35
• Also, on cell weights: are you only considering immediately adjacent lines above each cell, or all lines (up to the most vertically positioned line) above each cell? – Daniel Apon Sep 21 '10 at 16:46
• I'm confused by the last line: I assume the 'legal motion' problem is the one that's solvable in n^2 time, not the 'legal motion-exactly-once' problem ? – Suresh Venkat Sep 21 '10 at 17:06
• Daniel: Yes, in the Cartesian plane, and lines are infinite. Suresh: Both legal motions and legal monotone motions can be found in O(n^2) time, by considering the problem in the dual (the first formulation). – Jeffε Sep 21 '10 at 23:35
• Daniel: Cell weights are determined by ALL lines above the cell, not just adjacent lines. – Jeffε Sep 21 '10 at 23:37

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.

• Yeah, I should have seen this! – Jeffε Sep 22 '10 at 5:13

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.

• A line of very high positive slope that starts above all of the points and translates downwards will cross C before it crosses any of the other points. – David Eppstein Sep 22 '10 at 4:18
• Won't it cross D first? Because D is the left-most point in the set? – Vinayak Pathak Sep 22 '10 at 4:25
• No, this doesn't work. The solution requires the line to pass through either {D} or {A,C,D}, if only instantaneously. But {D} is illegal because D has negative weight, and {A,C,D} is impossible because B is inside the (closed) convex hull of the other three points. – Jeffε Sep 22 '10 at 5:22
• I don't get your objection. How can it pass through {A, C, D} simultaneously? – Vinayak Pathak Sep 22 '10 at 5:45
• No, this still doesn't work. Please draw the line at the precise moment of transition from position 2 {A,D} to position 3 {C,D}! At that precise moment, the line must pass through both A and C (and therefore also through B), which means it's in position {D}, which is illegal. – Jeffε Sep 22 '10 at 13:16