Feature #5: Densest Deployment

Description

Our cellular operator serves a rectangular region, which is present in the form of a 2D grid. The operator deploys base stations at different locations in the grid. We are given the locations of these base stations (towers), which are represented by the (x, y) coordinates. We want to determine the densest deployment region in our network. This region must be rectangular, with a base station located on each corner of it. Of all such rectangular regions, the densest deployment covers the minimum area. If there is no such rectangular subset, we should return 0.

Note: We can assume that these locations of the base stations are always unique.

Let’s review a few examples of this:

Solution

The brute-force approach would involve going over all the given coordinates, trying to form a rectangle, and calculating the area of the newly-formed rectangle.

Instead of following this approach, we can store the coordinates in a structured manner to reduce the number of iterations. We can observe an interesting thing about rectangles here: given two points of a rectangle, we can find out the remaining two points from a set of input points.

Suppose that we have two base stations, A and B, represented by the coordinates (x1, y1) and (x1, y2), respectively. Having fixed the locations of the base stations A and B, we can calculate the coordinates of base stations C and D, which can possibly form a rectangle:

• The y-coordinate of A and D should be equal.
• The y-coordinate of B and C should be equal.
• The x-coordinate of C and D should be equal.

...