What's a broken line?

dinoboy wrote: What's a broken line? A polygonal path, I suppose.

Yup.

The best bound for the length of a minimal path I came up with is $\left(\sqrt{2}+1\right)n$. Anybody with better bound?

Here's the $2n + 1$ bound they ask for; I suspect (given how dumb this algorithm is), we can do much better. Divide the square into $n$ columns of width $\frac{1}{n}$. Begin at the midpoint of the top base of the leftmost column, and proceed straight down to the midpoint of the bottom base. Each time you are at the same "y-coordinate" as one of the $n^2$ points, horizontally move straight out to it and then straight back to the middle, continuing straight down as before. When you reach the midpoint of the bottom base of the column, move straight to the midpoint of the lower base of the next column and continue upward. Keep snaking like this through the $n$ columns; we claim this path has length at most $2n + 1$. The amount we "depart" for any point is at most $2(\frac{1}{2n}) = \frac{1}{n}$ so for $n^2$ points this totals $n$. The distance we travel vertically is $n$ as well, one for each column. Finally, the horizontal distance we travel along bases is $\frac{n - 1}{n} < 1$. Then the path has length $2n + \frac{n - 1}{n} < 2n + 1$, as desired.

hyperbolictangent wrote: Here's the $2n + 1$ bound they ask for; I suspect (given how dumb this algorithm is), we can do much better. True. I suspect that the correct tight bound is probably $n+\text{something}$.

Surprisingly, this is not the case. See here

v_Enhance wrote: Let $n$ be a positive integer. Given $n^2$ points in a unit square, prove that there exists a broken line of length $2n + 1$ that passes through all the points. Allen Yuan Apparently the same as hyperbolictangent's solution? I'll post anyway because it's a nice problem Split the square into $n^2$ equal square pieces. Start with the mid-point of the base of bottom-left corner and climb up vertically. At any point, if we encounter a marked point having the same "altitude" as our current location we move to it horizontally, come back in the same way, and keep on marching upwards. At the end of each column, we shift to the next one. The vertical distance we've travelled is $\le 1$, the horizontal distance $\le n$ (a unit at max for each column), and the detours we took cost $\le 2 \cdot \tfrac{1}{2n} \cdot n^2=n$ units of length. Thus, we have travelled no more than $2n+1$ length and covered all marked points by our path. $\blacksquare$

Divide the square into $n$ horizontal sections of dimentions $\frac{1}{n}$ by 1. Simply moving in a snake shape over the midpoints of the sections while moving horizontally to access the points in each section suffices; between the sections we move by $\frac{n-1}{n}$ , vertically across each section we move by 1, and to ”catch” each point, we need to move at most $\frac{1}{2n}$ outwards and back from the midline of a section. $\frac{1}{2n} \cdot 2 \cdot n^2 + n \cdot 1 + \frac{n-1}{n} < 2n + 1$, and at last, draw a five-pointed star with the remaining $\frac{1}{n}$ length of the broken line.

Divide the unit square into $\frac1n \times \frac1n$ squares, and snake horizontally through squares, going to points as necessary. Then there is at most $n$ horizontal movement, and at most $n \cdot \left(\frac1n + \frac1n + \dots + \frac2n\right) = n + 1$ vertical movement.

very much xooking