<p>The time is essentially the same as that for sorting numbers in the range $1,\dots M$.</p>

<p>Graham scan (in the version where the points are sorted by their x-coordinates (with ties broken by y coordinates) rather than the one the textbooks unaccountably use in which they are sorted radially) can find convex hulls in linear time after the sorting step. So for your problem in which the coordinates are small integers, all the standard bounds of <a href="https://en.wikipedia.org/wiki/Integer_sorting">integer sorting</a> apply. In particular, radix sort can achieve time $O(n(1+\frac{\log M}{\log n}))$ (e.g. linear time whenever $M$ is at most polynomial in $n$), and a randomized sorting algorithm of Han &amp; Thorup 2002 can achieve time $O(n\sqrt{\log\log n})$. These are in models of computation in which machine words hold integers of some word length that is big enough to store the numbers $n$ and $M$ and in which one can do arithmetic and table lookups in constant time.</p>

<p>Conversely, you could use a convex hull algorithm to sort a set of numbers $x_i$, by finding the hull of the points $(x_i,x_i^2)$. So if you could do convex hulls any faster than this, you could also improve the times for integer sorting. (The range $M$ of $y$-coordinates of these points would be the square of the range of the numbers, but since all the time bounds involve logarithms of this range, squaring $M$ makes no difference in terms of the eventual $O$-notation.)</p>

CC BY-SA 3.0
2013-12-03T17:45:01.697Z
Thank you for your answer. I have some questions still. What do you mean by "sorted by their coordinate values"? Do you mean with lexicographic order or something like that? My second question is that you say that once the points are sorted, the convex hull can be computed in linear time: Do you mean linear in $n$? or in $M$? or both? I guess it is linear in $n$ and $\log M$ but I am not sure. It is of importance for me since contrary to what you write I am interested in the case of large coordinates!
Bruno
CC BY-SA 3.0
2013-12-03T18:22:25.920Z
I have clarified the sorting order. I mean linear in $n$, without any logs or other factors.
David Eppstein
CC BY-SA 3.0
2013-12-03T22:33:14.317Z
The original question explicitly asked for bit-complexity, but this answer provides complexity in the word RAM model.
Jeffε
CC BY-SA 3.0
2013-12-04T01:27:43.423Z
Well, true, but the same reasoning shows that the bit complexity of convex hulls is the same as the bit complexity of sorting, plus $O(n)$ orientation tests, up to constant factors. I was more addressing the part of the question that asked: what can you gain by assuming the inputs are integers?
David Eppstein
CC BY-SA 3.0
2013-12-04T09:39:37.493Z
I try to recap the different ingredients: First you have to perform integer sorting in essentially $O(n\log M)$ word operations. Then, you do $O(n)$ orientation tests. 

If I assume now that $\log M$ is larger than my word length, I guess we have to add $\log M$ factors to the complexity, right?
Bruno
CC BY-SA 3.0
2013-12-05T00:49:02.757Z
Mostly right, but I don't know where you get your bound of $O(n\log M)$ on the number of word operations for integer sorting. When $M$ is large that is worse even than standard comparison sorting algorithms. The number of word operations is as given in my answer: $O(n(1+\frac{\log M}{\log n}))$ or $O(n\sqrt{\log\log n})$. And the orientation tests involve multiplications, so they're a little more than $O(\log M\log\log M)$ per test.
David Eppstein
CC BY-SA 3.0
2013-12-03T17:26:30.927Z
2013-12-03T19:59:07.230Z
2013-12-03T19:59:07.230Z
David Eppstein
<p>Consider a set of $n$ points in $\mathbb Z^2$. It is known that <a href="https://en.wikipedia.org/wiki/Convex_hull_algorithms" rel="nofollow">their convex hull can be computed in time $O(n\log n)$</a>, or even $O(n\log h)$ where $h$ is the number of points in the convex hull. These bounds are in given (for instance) in the model of algebraic decision trees.</p>

<p><strong>What is the bit-complexity of computing the convex hull of $n$ points in $\mathbb Z^2$, whose both coordinates are bounded in absolute value by $M$?</strong> </p>

<p>I am interested on the one hand in the dependence of the complexity in $M$, and on the other hand in the possible gain in complexity one obtains using the fact that the input points have integer coordinates. In my problem, I see $M$ as a large parameter, that is $\log(M)$ has the same order of magnitude as $n$.</p>

<p>Note that I am especially interested in the problem with the additional requirement that the points on the convex hull have to be listed in the order of the (say) counterclockwise rotation, beginning for instance at the leftmost point.</p>

<p>I am also interested in the same questions in higher dimensions.</p>

CC BY-SA 3.0
2013-12-03T15:49:50.760Z
The convex hull has at most $O(M^{2/3})$ vertices, this might be useful for dense inputs.
Chao Xu
CC BY-SA 3.0
2013-12-03T15:56:35.547Z
@ChaoXu: Is this something obvious? I don't see why it is true... Or if it is not, do you have a reference? Thanks!
Bruno
CC BY-SA 3.0
2013-12-03T16:22:19.970Z
I don't have a short proof, I learned the fact from problem 4 here. http://sarielhp.org/research/algorithms/quals/03/03_fall.pdf Either way, we can get an algorithm with complexity of $O(M+n)$. Store the points with the largest and smallest $y$ coordinate for every $x$ coordinate. Do a Graham scan.
Chao Xu
CC BY-SA 3.0
2013-12-03T22:33:31.380Z
But each orientation test in Graham's scan require $O(\log M\log\log M\log\log\log M)$ bit operations each, assuming multiplication is implemented using Schönhage-Strassen.
Jeffε
<reference-request><cg.comp-geom>
Computing the convex hull of lattice points
Bruno
# Computing the convex hull of lattice points

(Asked by: username_0 on 2013-12-03)

Consider a set of $n$ points in $\mathbb Z^2$. It is known that [their convex hull can be computed in time $O(n\log n)$](https://en.wikipedia.org/wiki/Convex_hull_algorithms), or even $O(n\log h)$ where $h$ is the number of points in the convex hull. These bounds are in given (for instance) in the model of algebraic decision trees.

**What is the bit-complexity of computing the convex hull of $n$ points in $\mathbb Z^2$, whose both coordinates are bounded in absolute value by $M$?**

I am interested on the one hand in the dependence of the complexity in $M$, and on the other hand in the possible gain in complexity one obtains using the fact that the input points have integer coordinates. In my problem, I see $M$ as a large parameter, that is $\log(M)$ has the same order of magnitude as $n$.

Note that I am especially interested in the problem with the additional requirement that the points on the convex hull have to be listed in the order of the (say) counterclockwise rotation, beginning for instance at the leftmost point.

I am also interested in the same questions in higher dimensions.

**Tags:** reference-request, cg.comp-geom

> **Comments:**
> **username_1**: The convex hull has at most $O(M^{2/3})$ vertices, this might be useful for dense inputs.  
> **username_0**: @ChaoXu: Is this something obvious? I don't see why it is true... Or if it is not, do you have a reference? Thanks!  
> **username_1**: I don't have a short proof, I learned the fact from problem 4 here. http://sarielhp.org/research/algorithms/quals/03/03_fall.pdf Either way, we can get an algorithm with complexity of $O(M+n)$. Store the points with the largest and smallest $y$ coordinate for every $x$ coordinate. Do a Graham scan.  
> **username_2**: But each orientation test in Graham's scan require $O(\log M\log\log M\log\log\log M)$ bit operations each, assuming multiplication is implemented using Schönhage-Strassen.  

---

## 1 answers

### Answer by username_3 on 2013-12-03. Score: 10 | Accepted answer

The time is essentially the same as that for sorting numbers in the range $1,\dots M$.

Graham scan (in the version where the points are sorted by their x-coordinates (with ties broken by y coordinates) rather than the one the textbooks unaccountably use in which they are sorted radially) can find convex hulls in linear time after the sorting step. So for your problem in which the coordinates are small integers, all the standard bounds of [integer sorting](https://en.wikipedia.org/wiki/Integer_sorting) apply. In particular, radix sort can achieve time $O(n(1+\frac{\log M}{\log n}))$ (e.g. linear time whenever $M$ is at most polynomial in $n$), and a randomized sorting algorithm of Han & Thorup 2002 can achieve time $O(n\sqrt{\log\log n})$. These are in models of computation in which machine words hold integers of some word length that is big enough to store the numbers $n$ and $M$ and in which one can do arithmetic and table lookups in constant time.

Conversely, you could use a convex hull algorithm to sort a set of numbers $x\_i$, by finding the hull of the points $(x\_i,x\_i^2)$. So if you could do convex hulls any faster than this, you could also improve the times for integer sorting. (The range $M$ of $y$-coordinates of these points would be the square of the range of the numbers, but since all the time bounds involve logarithms of this range, squaring $M$ makes no difference in terms of the eventual $O$-notation.)

> **Comments:**
> **username_0**: Thank you for your answer. I have some questions still. What do you mean by "sorted by their coordinate values"? Do you mean with lexicographic order or something like that? My second question is that you say that once the points are sorted, the convex hull can be computed in linear time: Do you mean linear in $n$? or in $M$? or both? I guess it is linear in $n$ and $\log M$ but I am not sure. It is of importance for me since contrary to what you write I am interested in the case of large coordinates!  
> **username_3**: I have clarified the sorting order. I mean linear in $n$, without any logs or other factors.  
> **username_2**: The original question explicitly asked for bit-complexity, but this answer provides complexity in the word RAM model.  
> **username_3**: Well, true, but the same reasoning shows that the bit complexity of convex hulls is the same as the bit complexity of sorting, plus $O(n)$ orientation tests, up to constant factors. I was more addressing the part of the question that asked: what can you gain by assuming the inputs are integers?  
> **username_0**: I try to recap the different ingredients: First you have to perform integer sorting in essentially $O(n\log M)$ word operations. Then, you do $O(n)$ orientation tests.   If I assume now that $\log M$ is larger than my word length, I guess we have to add $\log M$ factors to the complexity, right?  
> **username_3**: Mostly right, but I don't know where you get your bound of $O(n\log M)$ on the number of word operations for integer sorting. When $M$ is large that is worse even than standard comparison sorting algorithms. The number of word operations is as given in my answer: $O(n(1+\frac{\log M}{\log n}))$ or $O(n\sqrt{\log\log n})$. And the orientation tests involve multiplications, so they're a little more than $O(\log M\log\log M)$ per test.  

---

