It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points.
And conversely, the deletion of a single point may produce the opposite drastic change of the size of the output.
There are data structures that can maintain representations of the convex hull in an amount of time per update that is much smaller than linear.
For many years the best algorithm of this type was that of Overmars and van Leeuwen (1981), which took time O(log2 n) per update, but it has since been improved by Timothy M. Chan and others.
The mentioned approach of Overmars and van Leeuwen allows for logarithmic complexity of various common queries.