The classical interval partition Problem ascs for a minimal colouring of an interval graph: Let [a_i, b_i] be a collection of (closed) intervals (for i in {1,2,...,n} ). Find a partition of {1,2,...,n} in subsets A_1, A_2, ..., A_k, such that the intervals corresponding to the indices in each set are pairwise disjoint and k is as small as possible. After a preprossecing of time nlogn to sort the intervals from left to right (according to the leftmost endpoint), a greedy algorithm (of time again nlogn) solves the Problem (this time is achieved if one uses a particular heap data structure to save the progress).

My question is now about the 2d analogous case. I want to partition a collection of 2d-boxes in k groups, each one of them containing only pairwise disjoint boxes and k being as small as possible (the analogous resulting graph is called "a graph of boxicity 2", if it helps).

An idea would be to first find an appropriate sorting of the boxes and then use a very similar greedy algorithm as in the 1D case) On that I have some thoughts:

1) For the preprocessing (aka sorting) one can define the following directed graph on the boxes: If B2 "shadows" B1 but does not intersect it, then B1 is "before" B2 and there is an edge from B1 to B2, i.e. the following function returns -1:

compare(box B1, box B2) {
    if(disjoint(B1, B2)) {
        if(B1.maxX<B2.minX || B1.maxY<B2.minY) return -1;
        else if(the symmetric) return 1; else return 0;
    else if(B1.maxX<B2.maxX && B1.maxY<B2.maxY) return -1; // also 0 would make sense
    else if(the symmetric) return 1; // here as well
    else return 0;

I think that the resulting graph is always acyclic, so the idea would then be to find a topological total order (which can be done in time O(n+m), if one knows the graph). My problem now is that I do not have the graph, I just have the boxes and I also have the above function I could use, through queries. A naive way to build this graph would be to ask all n^2 queries, which seems to spend a lot of unnecessary time (for a sparse enough graph, i.e. for m=o(n^2) ). So, question nb. 1: Is there any quicker way to define a total order on these boxes, that respects the above function? (intuitively, I'm looking for an order, for which if I take the i-th box, the only boxes having some endpoint to the left or up of any point in Bi are either boxes intersecting Bi, or boxes with smaller indices.

Another thought in the same direction is some kind of a merge sort, where the elements are lists of boxes that all do not have any edge between eachother. There, one should find a smart way to handle these lists and be able to "cut" such a list in half, if there is a box from another list, having some edges with these boxes, while performing a merge step.

2) For the actual greedy choice, after the preprossecing, the naive data structure would cost kn, which could be as bad as n^2.

Notice that in the 1D case there are two completely independent orders defined on the set of all intervals. The one is used in the preprocessing and the other at the min-heap. The ordering used at the heap is comparing the endpoints of the last intervals of each formed group. So, the greedy property is that a new interval goes always to the group of intervals that has the smallest last point of the last interval. If it does not start after this "best last point", one immediately forms a new group, without other comparisons.

Here, we again stumble against the problem of a "good box sorting". And a directed graph is not going to save me this time, because I cannot think of any way to combine this with a heap. So, question nb. 2: is there a quick way to accomplish this?

Of course, you can always answer question nb 3, instead: Does it exist an algorithm of time complexity o(n^2) to solve this problem? (when m is small)


Your Answer

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

Browse other questions tagged or ask your own question.