CODEWITHSUNDEEP
algorithmoptimizationdata-structuresconvex-hullconvex-optimization
porcupine
porcupine

Reputation: 43

Dynamic convex hull trick

I was reading about interesting algorithms in my free time and I just discovered the convex hull trick algorithm, with which we can compute the maxima of several lines in the plane on a given x coordinate. I found this article:

http://wcipeg.com/wiki/Convex_hull_trick

Here the author says, that the dynamic version of this algorithm runs in logarithmic time, but there is no proof. When we insert a line, we test some of his neighbors, but I dont understand how can it be O(log N) when we can test all the N lines by such an insert. Is it correct or I missed something?
UPDATE: this question is already answered, the interesting ones are the rest below

Thank you in advance!

Upvotes: 2

Views: 3186

Answers (3)

Eric Ouellet
Eric Ouellet

Reputation: 11753

Insertion can be quicker than O(log n), it can be achieve in O(Log h) where h is the set of already calculated Hull points. Insertion in batch or one by one can be done in O(log h) per point. You can read my articles about that:

  1. A Convex Hull Algorithm and its implementation in O(n log h)
  2. Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
  3. First and Extremely fast Online 2D Convex Hull Algorithm in O(Log h) per point

About delete: I'm pretty sure, but it has to be proven, that it can be achieve in O(log n + log h) = O(log n) per point. A text about it is available at the end of the my third article.

Upvotes: -1

kraskevich
kraskevich

Reputation: 18576

  1. The article claims amortized(not the worst case) O(log N) time per insertion. The amortize bound is easy to prove(each line is removed at most once and each check is either the last one or leads to a deletion of one line).

  2. The article does not say that this data structure supports deletions at all. I'm not sure if it is possible to handle them efficiently. There is an obstacle: the time complexity analysis is based on fact that if we remove a line, we will never need it in the future, which is not the case when deletions are allowed.

Upvotes: 1

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

To answer your first question: "How can insertion be O(logn)?", you can indeed end up checking O(n) neighbors, but note that you only need to check an extra neighbor when you discover that you need to do a delete operation.

The point is that if you are going to insert n new lines, then you can at most do the delete operation n times. Therefore the total amount of extra work is at most O(n) in addition to the O(logn) work per line that you need to find its position in the sorted data structure.

So the total effort for inserting all n lines is O(n) + O(nlogn) = O(nlogn), or in other words, amortized O(logn) per line.

Upvotes: 1

Related Questions