3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Are points $p_i$ supposed to be initially sorted? If so, there is a naive $O(n)$ algorithm (just check consecutive pairs). Also I don't think duality can be of any help here. $\endgroup$
    – Nathaniel
    Apr 11 at 0:00
  • $\begingroup$ Your assumption implies that if you group together runs of points of the same color, then there are $k+1$ runs. You can use a quicksort-like procedure to determine just the endpoints of the runs (in a sorted error) in time $O(nk)$, but I don't immediately see how to get it down to $O(n\log k)$. $\endgroup$ Apr 11 at 7:00
  • $\begingroup$ @Nathaniel point aren't in sorted order $\endgroup$
    – MRE
    Apr 11 at 8:56
1
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Suppose the input is $1B, 4B, 2B, 3R$ in that order. Won't your first approach delete $2B$ and so report $1B-3R, 3R-4B$ instead of the correct answer, $2B-3R, 3R-4B$? $\endgroup$ Apr 12 at 8:48
  • $\begingroup$ @j_random_hacker You're absolutely right, woops. $\endgroup$
    – orlp
    Apr 12 at 9:45
  • $\begingroup$ @MRE You may want to consider unaccepting my answer because in its current state it doesn't actually have a complete algorithm (only a conditional conjecture). $\endgroup$
    – orlp
    Apr 12 at 9:45
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is essentially the same algorithm as mine (before my current assumed but not proven existing 'middlemost group' operator I had median-of-medians) and has the same issue that makes it $O(n \log n)$ with median-of-medians. Consider the input array where the first 51% is red, then 51% of the remaining elements is blue, etc, alternating. Then $k = O(\log n)$ but the runtime will be $O(n \log n) = O(nk)$. $\endgroup$
    – orlp
    Apr 14 at 10:44
  • $\begingroup$ @orlp: This algorithm solves your example instance in $O(n)$ time overall. Call a subproblem "right-backbone" if it is on the path of right-children from root to rightmost tip, and "top-left" if it is the sibling of a "right-backbone" problem. Top-left subproblems in your example are all "simple" in that they consist of at most 2 blocks of alternating colours (red then blue or vice versa). At least one of the two halves will be monochromatic and so requires no further processing, so we get $T_{simple}(m) \le T_{simple}(m/2) + O(m)$, so the total time required to solve any "simple" problem ... $\endgroup$ Apr 15 at 3:48
  • $\begingroup$ ... of size $m$, including the work involved in solving all its left- and right-descendants, is $O(m)$. Top-left subproblems involve disjoint point sets, so they can all be solved in $O(n)$ total time. That leaves only the right-backbone subproblems: these are generally not simple, but because we have already accounted for all top-left subproblems, the remaining work to solve them also obeys $T_{rb}(m) \le T_{rb}(m/2) + O(m)$, so they also take $O(n)$ total time. $\endgroup$ Apr 15 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.