2 added 2 characters in body
source | link

Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = [a_1,b_1] \cup \cdots \cup [a_K,b_K].$$

Select $N \geq 2$ points $x_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min_{i \neq j} |x_i-x_j|.$$

In my case, the intervals are already disjoint and sorted ($a_1 \leq b_1 < a_2 \leq b_2 < \ldots < a_K \leq b_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30. Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals, or vs. intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C_i$ of the points are to be chosen from interval $[a_i,b_i]$, then

$$\sum_{i=1}^K C_i = N \\ \Delta = \min_{1 \leq i < j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$$$\sum_{i=1}^K C_i = N \\ \Delta = \min_{1 \leq i \leq j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$

ignoring the terms with denominator $0$ or $-1$. And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a_1$ and $b_K$ willcan always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.

Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = [a_1,b_1] \cup \cdots \cup [a_K,b_K].$$

Select $N \geq 2$ points $x_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min_{i \neq j} |x_i-x_j|.$$

In my case, the intervals are already disjoint and sorted ($a_1 \leq b_1 < a_2 \leq b_2 < \ldots < a_K \leq b_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30. Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals, or intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C_i$ of the points are to be chosen from interval $[a_i,b_i]$, then

$$\sum_{i=1}^K C_i = N \\ \Delta = \min_{1 \leq i < j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$

ignoring the terms with denominator $0$ or $-1$. And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a_1$ and $b_K$ will always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.

Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = [a_1,b_1] \cup \cdots \cup [a_K,b_K].$$

Select $N \geq 2$ points $x_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min_{i \neq j} |x_i-x_j|.$$

In my case, the intervals are already disjoint and sorted ($a_1 \leq b_1 < a_2 \leq b_2 < \ldots < a_K \leq b_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30. Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals vs. intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C_i$ of the points are to be chosen from interval $[a_i,b_i]$, then

$$\sum_{i=1}^K C_i = N \\ \Delta = \min_{1 \leq i \leq j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$

ignoring the terms with denominator $0$ or $-1$. And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a_1$ and $b_K$ can always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.

1
source | link

Simple algorithm to select separated points in closed intervals

Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = [a_1,b_1] \cup \cdots \cup [a_K,b_K].$$

Select $N \geq 2$ points $x_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min_{i \neq j} |x_i-x_j|.$$

In my case, the intervals are already disjoint and sorted ($a_1 \leq b_1 < a_2 \leq b_2 < \ldots < a_K \leq b_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30. Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals, or intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C_i$ of the points are to be chosen from interval $[a_i,b_i]$, then

$$\sum_{i=1}^K C_i = N \\ \Delta = \min_{1 \leq i < j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$

ignoring the terms with denominator $0$ or $-1$. And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a_1$ and $b_K$ will always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.