Tverberg's Theorem in the Plane

Visualization

How it Works

Overview of Tverberg's Theorem

Tverberg's theorem states that for a set S of n points in dimension d, we can partition them into r subsets, where n = (d+1)(r-1) + 1, such that there exists a point (not necessarily in n) which is inside the convex hull of all subsets. In other words, the convex hulls of all the subsets overlap.

In the Plane

Our specific focus is Tverberg's theorem in the plane, so dimension d is fixed at d = 2. This means that our relation between number of subsets r and the set's size is n = 3r - 2.

When considering only the plane, there are three types of subsets: those of size 1, size 2, and size 3. In this explanation, we'll generally refer to these types of sets by the form which their respective convex hulls take. (We're assuming points are in general position, so no two points are the same, and no three points are collinear.)

• The convex hull of a single point is simply that point.
• The convex hull of a pair of points is the line segment formed by those points.
• The convex hull of a triple of points is the triangle that they form.

So we can say that a partition is composed of some number of points plus some number of segments plus some number of triangles. We can restrict this further though:

• We can't have two points in a partition: they can't overlap without being the same point.
• We can't have three line segments in a partition: if two segments overlap at a given point, we can't guarantee that there's a third segment that contains the overlap point.
• We can't have two segments and a point: if two segments overlap at a given point, we can't guarantee that their overlap will be the point in the partition.

So we can have either two segments or one point. The rest of our subsets must be triangles. (If we used any polygons 'larger' than a triangle, we wouldn't have enough points to form r subsets.)

Birch Partitions

The basis of our algorithm for finding a Tverberg partition in the plane uses a paper proving a result similar to this in the plane. B.J. Birch's paper On 3n Points in a Plane shows that for 3n points, we can partition the points into n subsets of 3, such that the triangles formed by each subset all overlap.

Birch's method for finding a partition is as follows:

1. Find the center of the 3n points (not one of the points themselves).
2. Sort the 3n points by their angle relative to the center point, assigned each one an index i from 0 to 3n-1.
3. For t ∈ [0, n-1], triangle t is formed by the points where i % n == t.

Essentially, this method creates a triangle using the three points where each pair has n-1 points between them (in sorted order).

This method works because of a property of the center point of a set: all closed halfspaces bounded by the center point must contain at least a third of the total points, in this case n/3 points. Since each border-segment of each triangle has n-1 points between them, then there must be n+1 (including the segment bounds) points in the halfspace bounded by the line through the center which is parallel to this border-segment. If this is the case for all three borders of a triangle, then the triangle must contain the center.

Choosing a Center Point

Tverberg in the plane is a fairly similar problem, since most of our partition will be made up of triangles. It just has a tighter constraint, where one of the points must be within the intersection. In some cases we can choose one of the points as a center point, and use Birch's algorithm to find the triangles which bound it.

But for this to work, the point we choose must fulfill the same role as a center point. So we need to check the property of all lines through a point being a boundary for a closed halfspace with a third of the points:

• For each point c in S, test whether it's a center point:
  1. For each point p in S (other than c) test the line from c to p:
     • If there are less than (n-1)/3 points (i.e. a third not including c) on either side of the line, c is not a valid center; move on to the next value for c.
  2. If c is a large enough halfspace for the remaining points, then find the Birch partition for the remaining points based on c as a center.

In this case, the Tverberg partition is the triangle subsets formed by the Birch partition, plus the point c.

But in many cases, there is no point within the set which is valid for this property (e.g. the case of all points being convex).

Making a Center Point

Our other possible configuration for a Tverberg partition in the plane is a two line segments and a number of triangles. Essentially, we need to get all line segments, and test whether their intersection is a valid center for Birch's algorithm:

• For each set of four points a, b, c, d in S:
  1. Find the intersection i of line segments formed by a, b, c, d, if it exists.
  2. For each point p in S (other than a, b, c, d) test the line from i to p
     • If there are less than (n-4)/3 points (i.e. a third not including a, b, c, d) on either side of the line, i is not a valid center, move on to the next set of points.
  3. If the intersection i is a large enough halfspace for the remaining points, then find the Birch partition for the remaining points based on i as a center.

In this case, the Tverberg partition is the triangle subsets formed by the Birch partition, plus the two line segments formed by the points a, b, c, and d whose intersection was the center point i.