dx24816's blog

Convex Hull Trick Implementation
By dx24816, history, 6 years 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

»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

click

→ Reply
»
6 years 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

→ Reply