Anachor's blog

By Anachor, history, 3 years ago,

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?

• +73

 » 3 years ago, # |   -15 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, # ^ |   +8 No, I mean the number of vertices of the convex hull. So, a square would only have four vertices.
 » 3 years ago, # |   +14 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 →   +8 Nice, this allows us to construct testcases with O(N2 / 3) points on the hull.
 » 3 years ago, # | ← Rev. 2 →   +23 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, # ^ |   +16 Nice to see a paper by Jarník cited, as someone whose head managed to collide with his books.
 » 3 years ago, # | ← Rev. 2 →   +57 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, # ^ |   +2 Just FYI, in your first summation you probably want yk + 1 - yk.
•  » » » 3 years ago, # ^ |   0 I assume you meant replacing bk by bi and made the same error in your comment. That's correct. Thanks.