Anachor's blog

By Anachor, history, 3 years ago, In English

Suppose you have a set of lattice points each of whose coordinates lie in the interval [0, N]. I've heard that the number of points on the convex hull is O(N2 / 3). However, I cannot seem to be able to prove this. How can this be proven?

Also, how to generate testcases such that the convex hull contains as many points as possible?

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

»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I might have misunderstood, but if we take the 4 corner points (and have the remaining N-4 points inside), then their convex hull is a square with O(N) lattice points on every edge...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    No, I mean the number of vertices of the convex hull. So, a square would only have four vertices.

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

A heuristic approach: take all the irreducible lattice vectors in [0, a]2 for some a, and sort them by the angle. Now construct the lower right envelope by taking prefix sums of the sorted list of those vectors. Expected gain in both x and y coordinate per point is Θ(a), and the number of vectors should be Θ(a2). If you plug in , the last prefix sum is (Θ(N), Θ(N)), and the lower right envelope contains points.

As for the other direction, it seems hard. I couldn't find a coherent proof for the 2-dimensional case on the Internet.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Nice, this allows us to construct testcases with O(N2 / 3) points on the hull.

»
3 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

There's a paper in German ("Über die Gitterpunke auf konvexen Kurven" by Vojtěch Jarník) that proves a Θ(l2 / 3) bound for convex C1 curves F of length l with 0 ≤ F' ≤ 1.

If we have a convex polygon, we can draw a convex C1 curve through all its vertices and apply his result to each octant. (The length of the curve is O(N).) This gives a O(N2 / 3) bound for convex polygons.

Edit: The paper also talks about convex polygons. One result is that the maximum number of vertices a convex polygon with integer coordinates and circumference x can have is

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Nice to see a paper by Jarník cited, as someone whose head managed to collide with his books.

»
3 years ago, # |
Rev. 2   Vote: I like it +57 Vote: I do not like it

A simplified proof for the fact that a convex lattice polygon with coordinates in [0, N] has at most O(N2 / 3) vertices:

Let (x0, y0), ..., (xn, yn) be the vertices with (x0, y0) = (xn, yn). Let (ai, bi) = (xi + 1 - xi, yi + 1 - yi) be the i-th line segment. W.l.o.g. let (a0, b0), ..., (ak, bk) be the line segments with 0 ≤ ai ≤ bi (the ones in one octant). We'll only look at these segments. Note that

so there are at most N2 / 3 indices i with bi ≥ N1 / 3. Let's call those segments long and the other ones short. Let m + 1 be the number of short segments and (asj, bsj) be the j-th short segment. Then

so

On the other hand, by restriction on the octant and convexity of the polygon, the sequence is sorted, so using ai ≤ bi we get

so m ≤ 2N2 / 3 hence k ≤ 3N2 / 3. Summing up over all 8 octants, we get an upper bound of 24N2 / 3 for the number of vertices.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Just FYI, in your first summation you probably want yk + 1 - yk.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I assume you meant replacing bk by bi and made the same error in your comment. That's correct. Thanks.