dx24816's blog

By dx24816, history, 14 months ago, In English,

Hello,

I have recently been reading about the convex hull trick (https://wcipeg.com/wiki/Convex_hull_trick), but I can't seem to implement the fully dynamic version. Can anyone point me to a C++ implementation of the fully dynamic convex hull trick? Thanks!

-dx24816

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

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I use dynamic connectivity implementation and simple implementation of convex hull trick. You can see it here. It's O((n+q)logqlogn)

operations:

  • add

  • delete

  • query