Final answer:
To prove RECTANGLE ≤p CLIQUE, we construct a graph where vertices represent rectangles and edges exist if rectangles do not overlap. A clique of size n-k+1 in this graph implies a configuration where no more than k rectangles share a common point, thus transforming the RECTANGLE problem into the CLIQUE problem in polynomial time and proving the reducibility.
Step-by-step explanation:
To prove that RECTANGLE is polynomial time reducible to CLIQUE (notated as RECTANGLE ≤p CLIQUE), one needs to show that any instance of the RECTANGLE problem can be transformed into an instance of the CLIQUE problem in polynomial time in such a way that the original RECTANGLE problem has a solution if and only if the resulting CLIQUE problem does.
A 'clique' in graph theory refers to a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. With this in mind, we can create a graph where each vertex corresponds to a rectangle from the set R and there is an edge between two vertices if and only if the corresponding rectangles do not overlap. Now we need to find a clique of size n-k+1 in this graph because if such a clique exists, it means that there are n-k+1 rectangles that do not share a common point with any rectangle outside of this clique. Since we are told that no more than k rectangles can share a common point, this configuration validates that no common point is shared by too many rectangles from set R.
The transformation procedure, from checking the common point in a set of axis-aligned rectangles to finding a clique in a graph, can be performed in polynomial time because it involves a pairwise comparison between rectangles to set the edges, which requires O(n^2) operations. Thus assuming that the CLIQUE problem can be solved, this transformation equips us with a way to solve the RECTANGLE problem, hence proving that RECTANGLE ≤p CLIQUE.