Triangle partitioning

Question

This was a problem in the 2010 Pacific ACM-ICPC contest. The gist of it is trying to find a way to partition a set of points inside a triangle into three subtriangles such that each partition contains exactly a third of the points.

Input:

• Coordinates of a bounding triangle: (v1x,v1y),(v2x,v2y),(v3x,v3y)
• A number 3n < 30000 representing the number of points lying inside the triangle
• Coordinates of the 3n points: (x_i,y_i) for i=1...3n

Output:

• A point (sx,sy) that splits the triangle into 3 subtriangles such that each subtriangle contains exactly n points.

The way the splitting point splits the bounding triangle into subtriangles is as follows: Draw a line from the splitting point to each of the three vertices. This will divide the triangle into 3 subtriangles.

We are guaranteed that such a point exists. Any such point will suffice (the answer is not necessarily unique).

Here is an example of the problem for n=2 (6 points). We are given the coordinates of each of the colored points and the coordinates of each vertex of the large triangle. The splitting point is circled in gray.

Can someone suggest an algorithm faster than O(n^2)?

Answer 1

Here's an O(n log n) algorithm. Let's assume no degeneracy.

The high-level idea is, given a triangle PQR,

   P
  C \
 /  S\
R-----Q

we initially place the center point C at P. Slide C toward R until there are n points inside the triangle CPQ and one (S) on the segment CQ. Slide C toward Q until either triangle CRP is no longer deficient (perturb C and we're done) or CP hits a point. In the latter case, slide C away from P until either triangle CRP is no longer deficient (we're done) or CQ hits a point, in which case we begin sliding C toward Q again.

Clearly the implementation cannot “slide” points, so for each triangle involving C, for each vertex S of that triangle other than C, store the points inside the triangle in a binary search tree sorted by angle with S. These structures suffice to implement this kinetic algorithm.

I assert without proof that this algorithm is correct.

As for the running time, each event is a point-line intersection and can be handled in time O(log n). The angles PC and QC and RC are all monotonic, so each of O(1) lines hits each point at most once.

Answer 2

Main idea is: if we have got the line, we can try to find a point on it using linear search. If the line is not good enough, we can move it using binary search.

1. Sort the points based on the direction from vertex A. Sort them for B and C too.
2. Set current range for vertex A to be all the points.
3. Select 2 middle points from the range for vertex A. These 2 points define subrange for 'A'. Get some line AD lying between these points.
4. Iterate for all the points lying between B and AD (starting from BA). Stop when n points found. Select subrange of directions from B to points n and next after n (if there is no point after n, use BC). If less than n points can be found, set current range for vertex A to be the left half of the current range and go to step 3.
5. Same as step 4, but for vertex C.
6. If subranges A, B, C intersect, choose any point from there and finish. Otherwise, if A&B is closer to A, set current range for vertex A to be the right half of the current range and go to step 3. Otherwise set current range for vertex A to be the left half of the current range and go to step 3.

Complexity: sorting O(n * log n), search O(n * log n). (Combination of binary and linear search).