Finding all pairs of points with no point in between

Question

Suppose there are $n$ points $p_1,p_2,\dots,p_n$ with color red or blue on a line. We want to find all pairs $(p_i,p_j)$ whose color is distinct and such that there are no points between them. If there are $k$ pairs with the described property, design an algorithm with $O(n\log k)$ that uses idea of divide and pruning.

I think if we check all points we can solve this problem, but running time will exceed $O(n\log k)$.

I think for solving this problem we can use projective geometry duality, but I am stuck. Any help would be appreciated.

Answer 1

If you can select $p_j$ in $O(n)$ time such that it's part of the middlemost group of elements with the same color, the following algorithm works. However I haven't found such a prerequisite.

After finding $p_j$ we can do an $O(n)$ scan to find $p_k$, the minimal element $>p_j$ with the opposite color. We can do a similar scan for $p_i$, the maximal element $<p_j$ with the opposite color. Finally we can partition our array in $O(n)$ time into three subarrays, left ($\{\leq p_i\})$, middle (rest, all with same color as $p_j$), and right ($\{\geq p_k\}$).

In an analysis similar to quicksort you can prove that if we recursively apply the above partitioning to the left and right subarrays we end up with a call tree that has height $\log k$ and at each level of the tree we do a combined $O(n)$ operations, thus a total runtime of $O(n \log k)$.

Afterwards (or during) you can simply iterate over each adjacent partition and output the opposite colored pairs (because each partition is uniformly colored).

Answer 2

I believe the following simple algorithm is $O(n\log k)$-time, but I can't prove it because the subproblems are not guaranteed to stop on level $\log k$ of the recursion -- counterexamples, suggestions or direct edits welcome!

Splitting purple intervals

The basic idea is that we maintain a set of intervals containing both red and blue points (I'll call these purple intervals), initially consisting of a single interval containing all the points, and for as long as this set is not empty, we remove some interval from it, split it in half, and add back in whichever of these two halves are still purple (this may be 0, 1 or 2 intervals). Intervals generated along the way that contain only red or only blue points don't need to be subdivided further, and by the time no purple intervals are left, they partition the input into at least $k+1$ blocks of same-coloured points, from which the solution can be read off in $O(n)$ time.

By maintaining for each interval the list of points in that interval, an interval containing $m$ points can be split into two halves each containing at most $\lceil m/2 \rceil$ points in $O(m)$ time using the linear-time "median of medians" algorithm for finding medians. We can also determine in $O(m)$ total time whether each half is red, blue or purple: Loop over the $m$ points, incrementing one of four counters ($<$ median and blue, $<$ median and red, $\ge$ median and blue, $\ge$ median and red) for each. The lists of points for the two halves can be created in the same loop.

The splitting process can be represented as a binary tree, with nodes representing intervals and coloured red, blue or purple. The root node consists of the interval containing all points. Purple nodes have 0, 1 or 2 purple children, with the remaining children being red or green leaves that together partition the input points. All intervals on level $i$ have size $n/2^i$ and are disjoint; since a purple node implies at least one red-blue or blue-red colour change, there can be at most $k$ purple nodes on any level. I think this constraint is important for obtaining an $O(n\log k)$ time bound, but haven't figured out how to make use of it.