From the coding question Perfect Rectangles on leetcode.
Given an array $\text{rectangles}$ where $\text{rectangles}[i] = [x_i, y_i, a_i, b_i]$ represents an axis-aligned rectangle. The bottom-left point of the rectangle is $(x_i, y_i)$ and the top-right point of it is $(a_i, b_i)$.
Return $\text{true}$ if all the rectangles together form an exact cover of a rectangular region.
Many of the answers, such as this one, say a list of smaller rectangles form a cover as long as:
- The sum of areas of all smaller rectangles is equal to that of the encompassing rectangle.
- All corners other than the outer 4 appear an even number of times.
Initially, I understand that as long as the areas are equal and there is no overlap, then they form a cover. However, verifying whether there is no overlap is programmatically difficult. It seems that all corners appearing an even number of times implies there is no overlap, but I could neither prove nor disprove it.
That's a necessary condition as one can draw two rectangles inside the bigger one (overlapping and counting 4 (6) corners) and both have a total area of the rectangle. The necessary and sufficient condition is somehow trivial all rectangles do not overlap they have equal area sum of that of the bigger rectangle; then you should count an even number of corners if a corner belonging to some $2$ small rectangles corners is counted $2$ times.
Edit
The question is saying that the inside corners must belong to an even number of rectangles. And then the two conditions are correct since for any overlap with a covering set of rectangles (as in the figure) the corner inside and bounding the overlap appear a single time a contradiction. Of course this is also necessary drawing one then two three rectangles with same corner and parallel sides to span the rectangle.
In fact in the last step of the necessity there is a question whether such covering should have all sides of the small rectangles parallel to the bigger one.