zeref_dragoneel's blog

Online Convex Hull Trick
By zeref_dragoneel, history, 6 years ago, In English

Hi,

Let's say I have a set of lines, y = ax+b and three types of online queries:

  1. Given a and b, insert the line.
  2. Given a and b, delete the line (it is assured that the line exists)
  3. Given x0, print the maximum possible value of y.

(a is distinct for all the lines, a & b are integers.)

number of lines <= 1e5.

number of queries <= 3e5.

So O(log n / log^2 n / sqrt n) should work, according to me.

Can anyone help me with this?

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

If it's offline it's doable with LiChao segment tree in MlogMlog(Xmax * eps) about the same way you do dynamic connectivity: you support only insert operations on certain segments of activity (every segment is active from the moment it was inserted to the moment it got erased/the operations ended). Using LiChao segment trees you can also "take back" operations in logN (which can't be done with usual dynamic CHT).

I'm not aware of any solution for the online version of this problem, although I have thought about that intensively.

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

    Can you provide a link to read about LiChao segmant tree.

    Thanks.

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

      Here you can find a nice tutorial for LiChao Segment trees.

      As for the dynamic connectivity, you can learn more about it here and in the comments of the blog.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Your can also use normal incremental CHT: If you store one data structure per recursion level and apply the updates to the one on the current level, the undo operation can be done by clearing the one on the current level. At the leaves, you query all data structures (at most ) and take the maximum. This takes time in total. If you presort all updates and queries by x-coordinate, the linear-time data structure for monotone coordinates and queries that uses a deque instead of a set can be used, this achieves time overall.

    For the online version, switch to a dual space where the problem is

    • Insert the point (a, b).
    • Delete the point (a, b).
    • Query the extreme point the direction (x0, 1).

    To solve this, build a segment-tree (you might need one based on a BST for bigger coordinates) over the points sorted by x-coordinate where each node stores the upper convex hull in a persistent BST. When merging two nodes, we need to find the upper tangent of the convex hulls (as in the divide&conquer algorithm for convex hull), split the BSTs at the points where the tangents touch and join them. This can be done in by nesting two binary searches (one on the left and one on the right). Deletions and insertions are handled by the BST + recomputation along the insertion path by merging, they take each.

    To query, do a ternary search on the BST stored at the root. This will take time naively and can be sped up to if we each node stores it's successor in the persistent BST. The total memory consumption can be reduced to if each node reuses the same nodes for each merge done at it.

    The time for merging two upper hulls can be reduced to by a bunch of case-distinctions, see slides 20 — 30 here. This reduces the insertion and deletion time to .

    Finally, there's also an online solution with amortized time per insertion or deletion, see 'Dynamic Planar Convex Hull' by 'Riko Jacob', if you want to read 129 pages (I didn't).

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

      Can you explain in more detail your offline solution?

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Dynamic connectivity + dynamic convex hull you can achieve O(n * log2(n)).

Also sqrt(n) blocks, rebuild requiring block for updates, query each block and you can achieve O(n * sqrt(n) * log(n)).

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

    Can you elaborate on how to do it using Dynamic connectivity + dynamic convex hull?

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

      If you know what that mean, it's not a interesting solution. The main goal of connectivity is to get rid of delete updates.

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

    Doesn't work: when using dynamic CHT, you can't take back operations (because it has amortized complexity, not even if you use persistent BSTs) and you need that for dynamic connectivity.

    As for the second approach: it also works for online operations and its real complexity is sqrt (NlogN) which is not that bad (you an choose this as appropriate block size K and do update in O(K) and query in O(N/KlogN) as you can skip a logN when rebuilding, because you already have the list of lines sorted by their slope).

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

      Okay, you are right about both parts.

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

      Second approach: O(n sqrt n), build for each sqrt block and no consider erase query nodes, in the first build you should sort the array, but not in the last builds, you only sort sqrt nodes and merge.

      → Reply
»
6 years ago, # |
  Vote: I like it +58 Vote: I do not like it

Problem from ongoing contest

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    It is, but the contest problem is a little more specific with remove operations and easiest solution to code is different.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide any good tutorial link on convex hull trick.

→ Reply