I'm here as an engineer working on a point sampling algorithm and I've noticed that when I perform the algorithm on an ordered set of points in one direction it selects the exact same number of points as when I perform this algorithm in the opposite direction. It's not obvious from the algorithm that this should always be the case, but I've ran a simulation in python where I tested this property on 10 millions sets of 100 points with random intervals, and it seems to always hold true. I'd like to prove this.

I did my best to formulate it in a mathematical way:

Problem Formulation:

Let $L$ be a line segment representing a range $[a, b]$, where $a < b$ and $a, b \in \mathbb{R}$. On $L$, there is a set of points $P = \{p_1, p_2, \ldots, p_n\}$ such that $a = p_1 < p_2 < \ldots < p_n = b$.

Define an interval length $m$ where $m$ is greater than or equal to the smallest interval between consecutive points in $P$. Use the following selection process:

1. Start with the first point $p_1 = a$ and define an interval $[p_1, p_1 + m]$.
2. Identify the last point $p_k \in P$ within this interval such that $p_k \leq p_1 + m$, and add $p_k$ to a set $S$.
3. Repeat this process from $p_k$, defining each new interval starting from the last selected point and continuing until reaching $p_n = b$, adding selected points to $S$.
4. Similarly, start from $p_n = b$ and move leftward, defining intervals $[p_n - m, p_n]$ and adding selected points to a set $S'$.

Claim: The sizes of the sets $S$ and $S'$ are equal for any distribution of points in $P$.

In summary: the algorithm picks samples by going over an ordered set of points in sequence, and every time the distance to the last sample gets bigger than some maximum interval $m$, it selects the last point that was still within the interval, thereby guaranteeing that samples are never further apart than $m$. When executed backwards the algorithm often selects different points, yet the number of selected samples seems to always be the same. I have a hard time proving this and would appreciate any help.

I'm here as an engineer working on a point sampling algorithm and I've noticed that when I perform the algorithm on an ordered set of points in one direction it selects the exact same number of points as when I perform this algorithm in the opposite direction. It's not obvious from the algorithm that this should always be the case, but I've ran a simulation in python where I tested this property on 10 millions sets of 100 points with random intervals, and it seems to always hold true. I'd like to prove this.

I did my best to formulate it in a mathematical way:

Problem Formulation:

Let $L$ be a line segment representing a range $[a, b]$, where $a < b$ and $a, b \in \mathbb{R}$. On $L$, there is a set of points $P = \{p_1, p_2, \ldots, p_n\}$ such that $a = p_1 < p_2 < \ldots < p_n = b$.

Define an interval length $m$ where $m$ is greater than or equal to the largest interval between consecutive points in $P$. Use the following selection process:

1. Start with the first point $p_1 = a$ and define an interval $[p_1, p_1 + m]$.
2. Identify the last point $p_k \in P$ within this interval such that $p_k \leq p_1 + m$, and add $p_k$ to a set $S$.
3. Repeat this process from $p_k$, defining each new interval starting from the last selected point and continuing until reaching $p_n = b$, adding selected points to $S$.
4. Similarly, start from $p_n = b$ and move leftward, defining intervals $[p_n - m, p_n]$ and adding selected points to a set $S'$.

Claim: The sizes of the sets $S$ and $S'$ are equal for any distribution of points in $P$.

In summary: the algorithm picks samples by going over an ordered set of points in sequence, and every time the distance to the last sample gets bigger than some maximum interval $m$, it selects the last point that was still within the interval, thereby guaranteeing that samples are never further apart than $m$. When executed backwards the algorithm often selects different points, yet the number of selected samples seems to always be the same. I have a hard time proving this and would appreciate any help.