chromate00's blog

By chromate00, 17 months ago, In English

Let me state my opinions before we start the explaining the actual algorithm — I honestly prefer Monotone Chain over Graham Scan. Its simplicity in implementation is the most important reason, though I have other reasons such as the ability to find the upper hull and the lower hull separately. For people who are already accustomed to Rotating Calipers, you can do it the way you used to, and you will still find the same results. This algorithm is for the people who find the Rotating Calipers' concept hard to understand.

Just yesterday, I came up with a way to find the diameter of a polygon (the distance of the farthest pair) using Two pointers and Monotone Chain. I knew I could already do it using Rotating Calipers, but I found the concept quite hard to understand and implement. Therefore, I came up with a method myself. This method may be equivalent to Rotating Calipers in its result (I would be happy if I can extend it to other tasks), so remind me if it is.

First, we use the Monotone Chain algorithm to find the upper hull and the lower hull separately. Note that we are not looking for the entire hull in one array, we want the upper hull and the lower hull separately. This can be done using the usual Monotone Chain method, but instead of sweeping left->right->left, we sweep twice from left to right, once with $$$CCW \le 0$$$, and once with $$$CCW \ge 0$$$.

Now we prove the following theorem.

Theorem: The farthest pair of points in a polygon cannot be both placed on the upper hull (or vice versa, excludes the leftmost/rightmost point)

We will prove this by this idea: For every pair of points on the same side (upper/lower) of the hull, there exists a way to find a line containing the leftmost/rightmost point and one point from the original pair, with the length longer than the original. We have three cases based on the slope of the line segment (assuming upper hull): $$$a>0$$$, $$$a=0$$$, and $$$a<0$$$. For $$$a>0$$$, we can use the right side in the pair and the leftmost point. The distance in the x-axis and the y-axis will then both be farther than the original, resulting in a longer distance. For $$$a<0$$$ you can use the opposite, and for $$$a=0$$$ you can use either side. Same proof process for the lower hull. The following is a visualization of the proof process.

Green: The cases. Purple: The counterexamples.

Now we reverse the upper hull, and initialize $$$p_u$$$ and $$$p_l$$$ (stands for "upper pointer" and "lower pointer") both to $$$0$$$. So initially, $$$p_l$$$ points to the leftmost point, and $$$p_u$$$ points to the rightmost point. At each step, we update the maximum distance we've found so far, and check which pointer to advance. If $$$p_u$$$ is at the leftmost point, advance $$$p_l$$$. If $$$p_l$$$ is on the rightmost point, advance $$$p_u$$$. Otherwise, check $$$\text{dist}(p_u+1,p_l)$$$ and $$$\text{dist}(p_u,p_l+1)$$$. Advance to the side giving a greater value as a result. $$$\text{dist}(i,j)$$$ here denotes the distance (preferrably squared) between the $$$i$$$-th point on the upper hull (counting from the right) and the $$$j$$$-th point on the lower hull (counting from the left).

This algorithm will give a time complexity of $$$O(H)$$$, $$$H$$$ being the number of vertices on the hull. This algorithm has been tested on tasks which ask for this answer, including the famous "Robert Hood". I plan to release the code for it soon, after I finish some refactoring (the code is currently a bit ugly). Again, this algorithm may be simply equivalent to Rotating Calipers, so if you are already accustomed to it, please use what you are already convenient with. And if you could extend this idea to other Rotating Calipers tasks, let me know! I would be very interested.

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice job.Also, changing your profile color to blue from cyan when ?

17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

your algorithm is based on the wrong assumption that the farthest point is monotonic, which is known to be wrong as you can see here.

  • »
    17 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Then is there a formal proof that proves this algorithm's validity (or invalidity if there is a counterexample)? I would like to know.