Maximum clique of aligned boxes

Back to Geometric algorithms

Given is a set $P$ of (axis-aligned) boxes in $RR^d$ . A clique box is a box which is contained in the intersection of some subset $hat(P) sub P$ of boxes. The box maximum clique problem is to find a clique box such that $|hat(P)|$ is maximized. Such a box is then called a maximum clique box. There can be several maximum clique boxes, even if each box is made maximal.

Practice

Pastel implements an algorithm to find a maximum clique box in time $O(n log(n))$ , and to optionally report the subset $hat(P)$ using additional $O(|hat(P)|)$ time. The algorithm allows to choose whether to treat boxes as open or closed sets. Note that if one side of a box is open and the other side is closed, then the results are equivalent to both sides being open.

Multiple maximum cliques

In case there are multiple maximum cliques, the algorithm randomly samples through them and primarily maximizes the area, and secondarily (in case of equal area, especially zero area) the maximum width or height.

Example of local maximum clique sampling

Figure 1 demonstrates that, even in $RR^2$ , $n$ boxes can form $O(n^2)$ maximum cliques (here $n = 16$ ). In this image the red lines are boxes of width zero, and the there are four transparent blue boxes of thicker width. All of the box cliques are of size 2. It is easy to show for such a gridding of boxes that the probability that the algorithm returns a singular maximum clique box is given by $1 - (1 - 4 / n)^(n / 2)$ , which for $n = 16$ evaluates to $0.90$ . Furthermore, if we let $n$ grow, then this probability very quickly converges from above towards $1 - e^{-2} ~= 0.86$ . Thus with quite good probability the algorithm returns a non-singular maximum clique box. Similarly, the probability that the algorithm returns one of the four large-area maximum cliques is given by $1 - (1 - 4 / n)^2$ , which for $n = 16$ evaluates to 0.44, but approaches zero as $n$ grows.

Figure 1. n boxes forming O(n^2) maximum cliques.

Maximum clique of aligned boxes

Practice

Multiple maximum cliques

Example of local maximum clique sampling

Files

Maximum clique of an aligned box graph

Testing for aligned box maximum clique