4
$\begingroup$

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)$, 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.

$\endgroup$
  • 1
    $\begingroup$ The convex hull has at most $O(M^{2/3})$ vertices, this might be useful for dense inputs. $\endgroup$ – Chao Xu Dec 3 '13 at 15:49
  • $\begingroup$ @ChaoXu: Is this something obvious? I don't see why it is true... Or if it is not, do you have a reference? Thanks! $\endgroup$ – Bruno Dec 3 '13 at 15:56
  • 3
    $\begingroup$ I don't have a short proof, I learned the fact from problem 4 here. 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. $\endgroup$ – Chao Xu Dec 3 '13 at 16:22
  • 2
    $\begingroup$ 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. $\endgroup$ – Jeffε Dec 3 '13 at 22:33
10
$\begingroup$

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 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.)

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Bruno Dec 3 '13 at 17:45
  • 1
    $\begingroup$ I have clarified the sorting order. I mean linear in $n$, without any logs or other factors. $\endgroup$ – David Eppstein Dec 3 '13 at 18:22
  • 2
    $\begingroup$ The original question explicitly asked for bit-complexity, but this answer provides complexity in the word RAM model. $\endgroup$ – Jeffε Dec 3 '13 at 22:33
  • 1
    $\begingroup$ 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? $\endgroup$ – David Eppstein Dec 4 '13 at 1:27
  • $\begingroup$ 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? $\endgroup$ – Bruno Dec 4 '13 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.