Finding the Convex Polygon with the Largest Number of Vertices

In this article, I'll explain how to solve the following problem, which can be summarized as follows:

Given a finite set of non-collinear points in the first quadrant, find the convex polygon which has one vertex in the origin, and that has the largest number of vertices (by choosing some or all of the given points as vertices.)

Problem statement: Elastico - Beecrowd

Algorithm Design

Making the Polygon Convex

One of the most useful techniques used in geometry problems in competitive programming is using the cross product of two or more vectors to determine whether a polygon or part of it is convex or not.

Let \(a\) and \(b\) be two distinct points (both distinct from the origin), and \(\vec{a}\) and \(\vec{b}\) be their position vectors. Also, let's consider the \(\times\) operation to be the cross-product, but returning only the \(z\)-component scalar (this is a common but informal hack used in geometry involving 2D vectors.)

The two points are in counterclockwise order if:

$$\vec{a}\times\vec{b} > 0$$

The points are in clockwise order if:

$$\vec{a}\times\vec{b} < 0$$

And finally, the two points are collinear (with the origin) if:

$$\vec{a}\times\vec{b} = 0$$

Note that the last case can also happen if one or both vectors are zero vectors (i.e. all components are zero). Since this problem involves the origin, it's necessary to be careful about this.

This is enough to determine whether the polygon we are building remains convex or not. When we add a new vertex, we check using the cross product if the orientation of each vertex is correct.

There are several other applications of the cross-product in competitive programming, but they are out of the scope of this article.

Maximization

For the maximization (i.e. finding the polygon with the maximum amount of vertices), I used a dynamic programming approach, which will be explained next:

1. Use two-dimensional states: This means that the dp recursive function will have two parameters, current point and previous point. This is because it's not possible to know if the polygon will be convex just by knowing the current point.
2. Transition to every other point: By using the two parameters (current point and previous point), find all transitions to a next point where these three points keep the polygon convex.
3. Find the highest value: At all steps of the algorithm, keep the highest value found, and finally return the global maximum value.

Implementation

First, let's create a Point struct to make the rest of the program easier to write:

struct Point {
  int x, y;

  Point operator-(const Point& p) const { return Point{x - p.x, y - p.y}; }
  int cross(const Point& p) const { return x * p.y - y * p.x; }
  bool operator<(const Point& p) const { return cross(p) > 0; }
};

Note that operator< works as a comparator when sorting an array of points.

Then let's code the dynamic programming algorithm:

int dp(int p, int prev_idx) {
  if (memo[p][prev_idx] != -1) return memo[p][prev_idx];

  int ret = 0;

  const Point& curr = points[p];
  const Point& prev = points[prev_idx];

  for (int i = p + 1; i < (int)points.size(); i++) {
    const Point& next = points[i];

    Point prev_curr = curr - prev;
    Point curr_next = next - curr;

    if (prev_curr.cross(curr_next) > 0) {
      ret = max(ret, 1 + dp(i, p));
    }
  }

  return memo[p][prev_idx] = ret;
}

In order for this implementation to work, it's also necessary to perform some extra steps before calling the dp function.

• Sort the points (using the comparator defined above).
• Insert the origin \((0, 0)\) to the set. Note that I insert it at the beginning of the array after sorting. This is because my Point comparator function does not handle zero vectors correctly and because I want it to be the first element so that it's easier to know where it is (it could be anywhere, though).
• Execute dp for all points (otherwise, the global maxima won't be found), always having the origin as the previous point parameter.

sort(points.begin(), points.end());
points.insert(points.begin(), Point{0, 0});

int ans = 0;

for (int i = 1; i < (int)points.size(); i++) {
  ans = max(ans, 1 + dp(i, 0));
}

cout << (1 + ans) << endl;

The full solution in C++ can be found here.