In this post, we solve an algebraic geometrical problem using programming whereby we find the number of integral points between two given two points.

Table of contents:

1. Problem Statement
2. Explanation / Insight
3. Approach
4. Time and Space Complexity Analysis
5. Questions

Problem Statement

Problem Statement: Given two points A(x1, y1) and B(x2, y2), count the number of integral points between the two given points.

Input: A = {3, 17}, B = {48, 281}
Output: 2.

In other words, we are looking for lattice points between A(x1, y1) and B(x2, y2) or from B to A.

Explanation / Insight

Let starting and ending coordinates be (3, 17) and (48, 281) respectively.
The problem asks us to find number of lattice points, that is number of intersections of two or more gird lines which lie along this line joining the two coordinates.

The equation of this line will be;

$\frac{(\mathrm{x}-\mathrm{x}1)}{\mathrm{y}-\mathrm{y}1)}=\frac{(\mathrm{x}1-\mathrm{x}2)}{(\mathrm{y}1-\mathrm{y}2)}$

$\frac{(\mathrm{x}-3)}{(\mathrm{y}-17)} = \frac{45}{264}$

$\mathrm{x}=\frac{15}{88}*(\mathrm{y}-17)+3$

$y=\frac{88}{15}*(x-3)+17$

Every coordinate on the line A, B should now satisfy the above two equations.

x will be in the range of [3 - 48] , that is [3, 18, 33, 48] all multiples of 15 when subtracted by 3.

y will be in the range of [17 - 281] , that is [17, 105, 193, 281] all multiples of 88 when subtracted by 17.

Therfore all possible integral values of (x - 3) and (y - 17) will maintain the same ratio of not crossing x(45) an y(264),

All possible values will be the gcd(45, 264) = 3.
In our solution we exclude points A and B, 3 - 1 = 2.

Points to note

1. The number of points is equivalent to the gcd(abs(x2), abs(y1-y2)) - 1, Not inclusive of points A and B.
2. If the plane is parallel to the x-axis, that is x1 and x2 are equal (x1 == x2) the number of points is abs(y1 - y2) - 1.
3. If place is parallel to y-axis, that is y1 and y2 are equal, y1 == y2, the number of points is abs(x1- x2) - 1.

Approach

We can use loops to and check if a point lies on the line from A to B, if yes, we increment count although in this problem there are predefined formulas for solving such a problem as discussed above.

Optimal Approach

We use the formulas described above to do a simple computation an return the result.

Algorithm

The steps to find Number of integral points between two points are:

1. Initialize two points, A and B.
2. If they are parallel to x axis use the formula abs(y1 - y2) - 2
3. If they are parallel to y-axis, use abs(x1 - x2)
4. If they are not parallel to any axis, use th formula gcd(abs(x1 - x2), abs(y1 - y2)) - 1.
5. Return result.

#include<iostream>

using std::cout;
using std::endl;

//gcd helper function
int gcd(int a, int b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

int integralPoints(int A[], int B[]){
    //parallel to the x axis
    if(A[0] == B[0])
        return abs(A[1] - B[1]) - 1;
    //parallel to the y axis
    if(A[1] == B[1])
        return abs(A[0] - B[0]) - 1;
    //neither of the above conditions are satisfied
    return gcd(abs(A[0] - B[0]), abs(A[1] - B[1])) - 1;
}

int main(){
    int A[] = {0, 2};
    int B[] = {4, 0};
    cout << integralPoints(A, B) << endl;
    return 0;
}

Time and Space Complexity Analysis

The time complexity for the recursive gcd function is O(log(max(a, b)) which makes for the worst case, that is when we need to calculate it in the last condition otherwise the algorithm's time complexity is constant O(1). In the first two conditions we are just doing subtractions to obtain the results.

The space complexity is also constant O(1).

Questions

Another similar problem can be counting the number of integral points inside a triangle formed by 3 coordinates, do you see how to solve this problem?

With this article at OpenGenus, you must have the complete idea of finding the Number of integral points between two points.