# Finding the spots furthest away from bad data

The real-world problem I'm trying to solve is to create an algorithm which finds the ideal channels where I can transmit radio traffic, inside a radio frequency band that could contain various disturbances. These n ideal channels are those who are furthest away from any of the disturbances, but also the furthest away from each other. Where n is a constant picked by me, depending on how many channels the radio can support.

In abstract terms, I have a chunk of generic data where each item could either be labelled "good" or "bad". It can be considered to be an array of booleans, or illustrated as a series of 1=good and 0=bad, for example 0010111100.

In this data, consecutive sequences of good data form good segments:

0010111100   data size=10
^ ^
| +------- good segment 2, size 4
+--------- good segment 1, size 1


In the best case, there only exists one good segment covering all of the data:

1111111111   data size=10, 1 good segment with size 10


No matter the nature of the data, I need to find the n "best places" that are furthest away from any bad data, but also from each other. It is considered equally bad to be near a "bad" item as it is to be near another "best place".

The ideal solution is where the minimum distance between all "best places" and bad data/other best places is as long as possible, for all best places.

For example, in the case of 1111111111 where n=3 places, they could be located as follows (simply divide the data size by 3):

1111111111   data size=10, n=3
^  ^  ^


Or in case of 0110111110 n=3, the following would be fine:

0110111110   data size=10, n=3
^   ^ ^

or

0110111110   data size=10, n=3
^  ^ ^


In case there is too much bad data, the problem has no solution. The sum of all good segment sizes must be at least n or there exists no solution. Example:

0000010001   data size=10, n=3, no solution possible.


I suppose one solution is to find the n best segments out of all the good segments - then simply find the n best places at the center of those segments.

But one problem then is that there aren't necessarily n good segments. In that case, the best places have to be divided across what good segments there are.

Are there any similar existing algorithms that could be used or modified to suit the above scenario?

I'm also wondering if there is a particular data structure that would beneficial to use in this case, other than a raw array? A heap binary tree consisting of good segments?

• It sounds a lot like a factory location problem. Commented Jan 3, 2017 at 12:32
• You haven't clearly defined what counts as the best arrangement. What is the objective function you are trying to minimize/maximize? Minimize the sum of the squared distances between each pair of places? Maximize the minimum distance from any place to any other place or any bad location? Something else? Without that, the problem isn't well-defined.
– D.W.
Commented Jan 3, 2017 at 17:17
• @D.W. "Maximize the minimum distance from any place to any other place or any bad location" This. I'll edit to clarify. Commented Jan 4, 2017 at 7:55

I am going to assume you want to maximize the "separation". In particular, I'll say that a solution has separation $\ge s$ if every selected place is at least $s$ apart from any selected place, and if every selected place is at least $s$ away from any bad place.
Then this can be solved in $O(m \lg (m/n))$ time using binary search and a greedy algorithm, where $m =$ the data size. I'll show how to determine whether it's possible to place $n$ stations achieving separation $\ge s$, in $O(m)$ time; then you can use binary search on $s$ to find the largest $s$ achievable.
To determine whether separation $\ge s$ is achievable, just use a greedy algorithm with a left-to-right scan. Select the left-most place you can. Then, scanning left to right, select the first place that can be selected (taking into account it has to be at least $s$ to the right of the one you previously selected, and at least $s$ away from any bad place). Keep iterating. When you're done, that gives you the maximum number of places that can be selected, subject to the requirement that you have separation $\ge s$.
Now you can use binary search from here. If the number of places that could be selected was less than $n$, decrease $s$ and try again. If the number of places that could be selected was greater than or equal to $n$, increase $s$ and try again. There are at most $m/n$ possible values of $s$, so after $\lg (m/n)$ steps of binary search, this will terminate. If you start the binary search at the smallest possible value of $s$, the running time will be $O(m \lg s)$.
• @Lundin It depends on your goal. If you want to maximize the "minimum" distance between bad/selected channels, D.W.'s solution works fine and you don't need any extra effort. Even if you can find a channel with $s$ on one side and $>s$ on the other side, the solution is still optimal since we know $s+1$ doesn't work. In other word, it's not the bottleneck. If you need a tiebreaker you should formally define it. Commented Jan 4, 2017 at 11:08
• @Lundin Why do you think it matters? The algorithm works well if the size is not divisible by anything. What the algorithm do is packing as many good channels as it can (possibly $>n$), while guaranteeing distance $\ge s$ at the same time. Commented Jan 4, 2017 at 13:04