Dynamic Maintenance of the Lower Envelope of Pseudo-Lines

Pankaj K. Agarwal, Ravid Cohen, Dan Halperin +1

We present a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines. The structure has $O({\log }^{2}n)$ update time and $O(\log n)$ vertical ray shooting…