Problem

Submissions

Solution: Minimum Number of Lines to Cover Points

Statement▼

Given a 2D integer array, points, where points[i] $= [x_i,y_i]$ represents a point on an XY plane, find the minimum number of straight lines required to cover all the points.

Note: Straight lines will be added to the XY plane to ensure that every point is covered by at least one line.

Constraints:

$1\leq$ points.length $\leq10$
points[i].length $== 2$
$-100\leq$ $x_i, y_i$ $\leq100$
All the points are unique.

In this solution, we are solving a computational math and geometry problem of finding the minimum number of straight lines required to cover all given points in an XY plane. Let’s break down the logic, incorporating key mathematical reasoning and geometric approaches.

Slope and y-intercept

Two parameters can uniquely identify a straight line:

Slope: Determines the line’s steepness and direction, indicating how much the line rises or falls for a given horizontal change.
y-intercept: Specifies where the line crosses the y-axis.

For two points, $(x_1,y_1)$ and $(x_2,y_2)$ , the $\text{slope}$ $a$ is calculated as:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space a= \dfrac{(y_2−y_1)}{(x_2−x_1)}$

The y-intercept, $b$ , can then be found using the formula below:

Note: These above two parameters uniquely define a line on the XY plane. For vertical lines $(x_1=x_2)$ , the $\text{slope}$ is undefined, and we handle such cases separately by using $\text{slope}$ = $x_1$ with $\text{y-intercept}$ = $\infty$ .

Using the slope to identify collinear points:

A single line can pass through multiple points if they are collinear (on the same line). Or, we can say that two or more points are collinear if they share the same slope when paired. Calculating the slopes between points allows us to group points on the same line. As collinear points share the same slope and y-intercept, the problem reduces to finding sets of points with identical slope and y-intercept values.

This grouping is key to identifying and storing the lines in the solution.

Handling lines with more than two points:

Initially, we know at least $⌈n/2⌉$ lines are needed to cover all $n$ points, as each line can cover at most $2$ points in the worst case (if no three points are collinear). However, we focus on lines that cover more than two points to minimize the total number of lines required. These lines allow us to reduce the overall number of lines by maximizing coverage.

For lines covering more than $2$ points, we aim to find the smallest subset of lines that covers all points. This is achieved using bit masking for evaluate all subsets of lines.

Subset representation:

For $m$ lines with more than $2$ points, there are $2^m$ subsets:

Each subset is represented by a binary number of $m$ bits.
A bit value of $1$ means the corresponding line is included in the subset, while $0$ means it is excluded.

For example, with $m=2$ lines:

$01$ : Includes only the $1^{\text{st}}$ line.
$10$ : Includes only the $2^{\text{nd}}$ line.
$11$ : Includes both lines.

Processing subsets using bit masking:

We track the points covered by the selected lines in a subset. For each subset:

We iterate through each bit in its binary representation and evaluate its coverage by checking if the current bit is 1. If it is, we store all points covered by that line to the tracking set of currently covered points. Otherwise, we skip that line.
Next, we calculate uncovered points by subtracting the number of covered points in the tracking set from the total number of points, $n$ .
The total number of lines required is calculated as follows:

The final result is the minimum of $\text{total lines}$ across all subsets.

Here’s the step-by-step implementation of the solution:

Initialize a dictionary, line_points, to store the unique points on a respective line.
Iterate through all the pairs of points and for each current point (x₁, y₁):
1. Fix (x₁, y₁) and iterate for all the other remaining points (x₂, y₂), calculate slope and y_intercept of pairs (x₁, y₁) and (x₂, y₂).
  1. If x₁ == x₂, meaning both points lie vertically:
    1. The slope becomes x1, and the intercept will be $\infty$ because vertical lines have an undefined slope.
  2. Otherwise, calculate slope and y_intercept.
  3. Add these values to line_points with slope and y-intercept as the key and the respective points as the value.
Initialize an array, lines, to store the slope and y_intercept of the lines having more than $2$ points.
Initially, initialize the answer with the $⌈n/2⌉$ because minimum $⌈n/2⌉$ lines can cover any number of points.
Initialize m with the length of the lines having more than $2$ points.
Now, initialize a mask for all the subsets of the m, which are 2^m:
1. Initialize count_of_1s with the number of in the mask.
2. Initialize a set, current_points, to store the current subset of the line. Also, initialize a variable j to $0$ , to keep track of the current bit.
3. While the mask is not $0$ :
  1. If the last bit (rightmost bit) of the mask is $1$ :
    1. Add the points covered by the line to current_points.
  2. Shift the bits of mask one position to the right.
  3. Increment j to point to the next bit.
4. Calculate the uncovered_points by subtracting the current_points from total points n.
5. Update the answer by calculating the min(answer, count_of_1s + ⌈uncovered_points/2)⌉).
Return answer, which now represents the minimum number of lines to cover all points.

Let’s look at the following illustration to get a better understanding of the solution: