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

<p>I think the answer is No.</p>

<p>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 -</p>

<p>A: +10
B: -100
C: +500
D: -5</p>

<p>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.</p>

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

<p><img src="https://i.sstatic.net/jKFJi.jpg" alt="alt text"></p>

<p>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.
<img src="https://i.sstatic.net/pnQmd.jpg" alt="alt text"></p>

CC BY-SA 2.5
2010-09-22T04:18:50.970Z
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
CC BY-SA 2.5
2010-09-22T04:25:08.477Z
Won't it cross D first? Because D is the left-most point in the set?
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T05:22:42.200Z
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ε
CC BY-SA 2.5
2010-09-22T05:45:36.850Z
I don't get your objection. How can it pass through {A, C, D} simultaneously?
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T05:59:10.707Z
In case you are saying that a legal motion does not exist, I have added a figure showing the legal motion.
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T12:51:42.017Z
I like this small counterexample.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T13:16:22.473Z
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ε
CC BY-SA 2.5
2010-09-22T13:56:42.610Z
@JeffE: Now I understand your objection.  Thanks!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T14:33:12.863Z
@Jeff - Yes, it doesn't work. Sorry.
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T04:04:38.387Z
2010-09-22T05:58:20.693Z
2010-09-22T05:58:20.693Z
Vinayak Pathak
<p>The answer is no, me think.</p>

<p>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:</p>

<pre>
------------------------

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

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

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

--------------------------
</pre>

<p>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. 
<br>
Here is a figure:
<br></p>

<p><a href="https://i.sstatic.net/wVdU9.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wVdU9.gif" alt=""></a><br>
<sub>(source: <a href="http://valis.cs.uiuc.edu/~sariel/misc/blog/10/09/21/criss_cross.gif" rel="nofollow noreferrer">uiuc.edu</a>)</sub>  </p>

<p><br>
(<a href="https://sarielhp.org/misc/blog/10/09/22/criss_cross.ipe" rel="nofollow noreferrer">Ipe</a> source.)
<br>
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.</p>

CC BY-SA 2.5
2010-09-22T05:13:58.570Z
Yeah, I should have seen this!
Jeffε
CC BY-SA 4.0
2010-09-22T04:16:25.607Z
2019-07-14T12:17:06.617Z
2019-07-14T12:17:06.617Z
Sariel Har-Peled
<p>This is a followup to my <a href="https://cstheory.stackexchange.com/questions/1399/positive-topological-ordering-take-2">followup</a> to <a href="https://cstheory.stackexchange.com/questions/1346/positive-topological-ordering">David's question</a>.  This question admittedly leaves the original motivation far behind, but it might provide some useful intuition.</p>

<p>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 <em>arrangement</em>.  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.  </p>

<blockquote>
  <p>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 <em>and
  crosses each line exactly once</em>?</p>
</blockquote>

<p>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 <em>legal</em> if at all times, the total weight of the points above the line is non-negative.  </p>

<blockquote>
  <p>If there is a legal motion, must there
  be a legal motion where the moving
  line passes over each point <em>exactly
  once</em>?</p>
</blockquote>

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

CC BY-SA 2.5
2010-09-21T16:35:59.207Z
Just some clarification: Are these lines in a Cartesian plane? Do they have (x,y) endpoints?
Daniel Apon
CC BY-SA 2.5
2010-09-21T16:46:06.087Z
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
CC BY-SA 2.5
2010-09-21T17:06:32.883Z
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
CC BY-SA 2.5
2010-09-21T22:24:29.450Z
Is there a characterization for curves with the property that for each point on the curve, there exists a line that passes through only that point and no other point on the curve? By 'characterizaion', I just mean some simpler way of describing them.
Vinayak Pathak
CC BY-SA 2.5
2010-09-21T23:35:44.657Z
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ε
CC BY-SA 2.5
2010-09-21T23:37:46.667Z
Daniel: Cell weights are determined by ALL lines above the cell, not just adjacent lines.
Jeffε
<cg.comp-geom>
Paths in a weighted line arrangement
Jeffε
# Paths in a weighted line arrangement

(Asked by: username_0 on 2010-09-21)

This is a followup to my [followup](https://cstheory.stackexchange.com/questions/1399/positive-topological-ordering-take-2) to [David's question](https://cstheory.stackexchange.com/questions/1346/positive-topological-ordering). 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.)

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: Just some clarification: Are these lines in a Cartesian plane? Do they have (x,y) endpoints?  
> **username_1**: 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?  
> **username_2**: 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 ?  
> **username_3**: Is there a characterization for curves with the property that for each point on the curve, there exists a line that passes through only that point and no other point on the curve? By 'characterizaion', I just mean some simpler way of describing them.  
> **username_0**: 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).  
> **username_0**: Daniel: Cell weights are determined by ALL lines above the cell, not just adjacent lines.  

---

## 2 answers

### Answer by username_6 on 2010-09-22. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: Yeah, I should have seen this!  

---

### Answer by username_3 on 2010-09-22. Score: 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.

![alt text](https://i.sstatic.net/jKFJi.jpg)

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.
![alt text](https://i.sstatic.net/pnQmd.jpg)

> **Comments:**
> **username_4**: 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.  
> **username_3**: Won't it cross D first? Because D is the left-most point in the set?  
> **username_0**: 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.  
> **username_3**: I don't get your objection. How can it pass through {A, C, D} simultaneously?  
> **username_3**: In case you are saying that a legal motion does not exist, I have added a figure showing the legal motion.  
> **username_5**: I like this small counterexample.  
> **username_0**: 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.  
> **username_5**: @JeffE: Now I understand your objection.  Thanks!  
> **username_3**: @Jeff - Yes, it doesn't work. Sorry.  

---

