Convex Hull

In computational geometry, Convex Hull or Convex Polygon is a very common term and we face many problems which require the construction of a Convex Hull to generate desired solution.

A convex hull is a convex polygon which has the minimal area to contain the set of given points. In other words, for a given set of points, a Convex Hull is such a Convex Polygon that, every point on the set is either on the Polygon or inside the Polygon.

So, a typical problem might ask, "You are given n integer co-ordinates (3 ≤ n ≤ 10⁵), find the Convex Hull". It means it wants you to write down the co-ordinates of the picks or, find the convex area, or, find the center of gravity of it, or, sometimes, you are asked to create an arbitrary convex hull, or you may be asked, find whether a given point is inside a convex hull, and so on... Well, before getting into the harder ones, lets see how we can construct a convex hull smartly :P

There are a number of ways to compute convex hull from the given points. Like, I found those in wikipedia, (I know only three of them):

• Direct method
• Gift Wrapping (Packaging) method
• Graham's scan method
• Incremental (Sequential addition) method
• Divide and Conquer method
• Quick method (related to Quick Sort)
• Inner point elimination

The graham scan method is the most widely used method that has a complexity of O( n lg n ) for n points. In this method, the algorithm starts from a extreme (topmost / leftmost / rightmost / bottommost) point and keep wrapping all the other points unless it reaches the beginning point. Here's a little animation that shows it:


For detailed reading, you can visit Wikipedia or read Introduction to Algorithm - CLRS. Here's my implementation for finding Convex Hull with the help of Graham Scan method (integer points only):

#include <algorithm>
using namespace std;

#define MAX 100009
#define i64 long long
#define sq(x) ((x)*(x))

struct point {
    i64 x, y;
} P[MAX], C[MAX], P0;

// P[] contains all points
// C[] contains convex hull ccw

inline i64 TriArea2(point a, point b, point c) {
    return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
}

inline i64 sqDist(point a, point b) {
    return (sq(a.x-b.x) + sq(a.y-b.y));
}

bool comp(point a, point b) {
    i64 d = TriArea2(P0, a, b);
    if(d<0) return false;
    if(!d && sqDist(P0, b) > sqDist(P0, a)) return false;
    return true;
}

void ConvexHull(int np, int &nc) {
    int i, j, pos = 0;
    for(i=1; i<np; i++)
        if(P[i].y<P[pos].y || (P[i].y==P[pos].y && P[i].x>P[pos].x))
            pos = i;
    swap(P[0], P[pos]);
    P0 = P[0];
    sort(&P[1], P+np, comp);
    C[0] = P[0], C[1] = P[1], C[2] = P[2];
    for(i=j=3; i<np; i++) {
        while(TriArea2(C[j-2], C[j-1], P[i]) <= 0) j--;
        C[j++] = P[i];
    }
    nc = j;
}

Here,
TriArea2() returns the double of triangular area formed by the three points passed as its argument.
sqDist() returns the square distance between two points passed as its argument.
sort() is stl sort that sorts the P[] array according to their slope.
The first loop in ConvexHull() finds the starting point, i.e. the bottommost and rightmost point. After sorting rest of the points correctly, the second loop examines which point is to be added to the Hull. Finally nc is the number of points in convex hull updated via reference. There is no checking for n < 3 or if there are duplicates (actually if number of distinct points are ≥ 3, it doesn't matter in this method), we need to handle that according to problem requirement.

Not much tough as it seems to be ... happy coding

C/C++ Array of Functions

Oh, never thought of it? well, this is actually not array of functions, this is array of function pointer. You know, in C/C++, pointers are very powerful tools for accessing and allocating memory, and anything that has a logical entity in any type of memory, a pointer can access it pretty easily and this feature made all other languages jealous that they say allowing pointers are threat-full, lolzzz....

Well, here is a simple code presented that shows the use of such an array. Actually, we all know, like a character array s[100], s is the pointer to it, similarly, a function defined as f(int a), f is the pointer to it. Well, enough talk, lets examine the code...

#include <stdio.h>

inline int add(int a, int b) {
    return a + b;
}

inline int sub(int a, int b) {
    return a - b;
}

inline int mul(int a, int b) {
    return a * b;
}

inline int div(int a, int b) {
    return a / b;
}

inline int mod(int a, int b) {
    return a % b;
}

int main() {
    int (*func_array[])(int, int) = {&add, &sub, &mul, &div, &mod};
    for(int i=0; i<5; i++) printf("%d\n", func_array[i](10, 5));
    return 0;
}

Easy as usual...

Primitive Root

Primitive root modulo n

This time, lets talk about some sort of modular arithmetic. Suppose, you are asked a peculiar question like the following:

"For a prime number p, check whether g, g², g³, ... , g^p-1 are all distinct (mod p)." [ No doubt, here, p is sufficiently large to prevent you from following naive approach ]

In other words, you are asked:

"Given any prime number p, and another positive number g, you are to tell whether g is a primitive root modulo p."

Now the question is, what is a Primitive Root?

A positive integer g is said to be a primitive root modulo n, if for every integer h such that h and n are co-prime, i.e. GCD(h,n) = 1, there is an integer k such that g^k ≡ h (mod n). This also means, g is a generator of the multiplicative group of integers modulo n.

According to the above problem, here, n is actually any prime number p, which makes the condition GCD(h,p) = 1 very obvious.

Example:

The number 3 is a primitive root in (mod 7) because

3¹=3 ≡ 3 (mod 7)
3²=9 ≡ 2 (mod 7)
3³=27 ≡ 6 (mod 7)
3⁴=81 ≡ 4 (mod 7)
3⁵=243 ≡ 5 (mod 7)
3⁶=729 ≡ 1 (mod 7)

The remainders above which are 3, 2, 6, 4, 5, and 1 are simply a permutation of 1, 2, ..., (p-1). In this case, p-1=6 because the prime number is 7.

Now, how to solve the problem easily?

As far as I know, there is no simple formula known yet to find primitive roots, however, there is a faster way to test whether a number is a primitive root rather than simply trying out all candidates. This technique can be derived from the definition of primitive roots. From its alternate definition, we know, if the multiplicative order of a number g modulo n is equal to φ(n), then g is a primitive root. In fact, the converse is also true, g is a primitive root modulo n if the multiplicative order of g is φ(n). From this axiom, we get a way to test whether, for any given g and n, g is a primitive root modulo n, as follows:

• First we compute φ(n), [ In case n is a prime p, φ(n) = p-1 ]
• Factorize φ(n), let it has k different prime factors p₁, p₂, ... , p_k, [ Even if m is as large as 2³¹, k will be around 32 ]
• Compute g^φ(n)/p_i mod n; { for i = 1, 2, 3, ... ,k }. Using a successive squaring algorithm, this can be done very easily and fast. If all the k results are different than 1, then g is a primitive root modulo n.

hu la la... , really easy. From programming approach, φ(n) can be calculated easily by standard division algorithm, dividing by the primes less than √n. [ obviously we can use Sieve of Eratosthenes to get a prime table up to √max, and if n is a prime, φ(n) = n-1 ]. Then factorize φ(n) with the same standard division algorithm and get k different primes p_i, { for i = 1, 2, 3, ... , k }. Then the rest can be done in linear time to k where each k modular exponentiation is of logarithmic complexity.

Have fun ...

Confidence, Trust and Hope

A bit unusual words...

Confidence:

Once all the villagers decided to pray for the rain. On the day of prayer all the people gathered around and only one boy came with an umbrella. That's confidence.

Trust:

Trust should be like the feeling of a one year old baby. When you throw him in the air, he laughs because he knows you will never let him fall.

Hope:

Every night you go to bed with no assurance to wake up alive in the next morning. But still you make plans for the next day. How could you live if you did not have hope for tomorrow?

So be confident, trust in your abilities, never loose hope and do your best whatever you do to make the world more colorful...