1
$\begingroup$

Q. Do shortest paths walking between rational points of height $h$ ever properly cross themselves?

Explaining this question takes a bit of definitional exposition.

First, I copy definitions from an earlier question, "Circles avoiding rational points of height ≤h." A rational point in $\mathbb{R}^2$ is a point whose coordinates are both rational numbers. A rational number $x= a/b$ in lowest terms (i.e., gcd$(a,b)=1$) has height $\max \lbrace |a|,|b| \rbrace$. A rational point of height $h$ is a rational point whose coordinates are both of height $\le h$.

Now we take as our domain all the rational points in $(0,1)^2$, and define a metric on the set of pairs $(a, h(a))$. Let $$d(a,b) = \|a-b\| \cdot \tfrac{1}{2} {\left(h(a) + h(b) \right)} \;:$$ the Euclidean distance between $a$ and $b$ times their average $h$-height, i.e., the area of the "fence" under the $(a,h(a)){-}(b,h(b))$-path.

Now imagine seeking the shortest path between two points $a,b \in (0,1)^2$ under this metric. For example, here is one path from $(\frac{1}{8} , \frac{1}{6})$ to $(\frac{7}{8} , \frac{7}{8})$:


      SpPthRational
      $$ \left( \frac{1}{8} , \frac{1}{6} , 8 \right) \;, \left( \frac{1}{6} ,\frac{1}{2} , 6 \right) \;, \left( \frac{1}{3} , \frac{1}{2} , 3 \right) \;, \left( \frac{7}{8} , \frac{7}{8} , 8 \right). $$
      Heights of points shown circled.
The path illustrated is shorter than the direct, one-step path from $(\frac{1}{8},\frac{1}{6})$ to $(\frac{7}{8},\frac{7}{8})$ (but it is not the shortest path).

Does a shortest $ab$ path ever properly cross itself, in the sense that the "fences" (properly) intersect?

(Of course adjacent fences share a vertical edge.) Perhaps the answer is Yes but I don't see a counterexample. Generally shortest paths do not properly cross, which is one reason I think this could be interesting.

$\endgroup$
  • 2
    $\begingroup$ I found your notation confusing and would not have understood without the diagram .I think you should say "We take our (metric) space to be the set of pairs $ (a,h(a))$ for all rational points $ a \in (0,1)^2$." And define $d$ accordingly. Then the meaning of $a_2$ is clear. And I believe you wish to show the fences don't intersect except at their edges. Can you do anything with reverse induction, on the number of crossings, or the number of jumps, in a counter-example? $\endgroup$ – DanielWainfleet Nov 1 '15 at 4:57
  • $\begingroup$ @user254665: Your notation is superior. I have revised the question. Thanks. $\endgroup$ – Joseph O'Rourke Nov 5 '15 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.