INCREMENTAL ALGORITHMS FOR FINDING THE CONVEX HULLS OF CIRCLES AND THE LOWER ENVELOPES OF PARABOLAS

The existing O(n log n) algorithms for finding the convex hulls of cir cles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental algorithms for t hese problems is that the introduction of a new circle or parabola can cause Theta(n) structural changes, leading to Theta(n(2)) total struc tural changes during the running of the algorithm. In this note we exa mine the geometry of these problems and show that, if the circles or p arabolas are first sorted by appropriate parameters before constructin g the convex hull or lower envelope incrementally, then each new addit ion may cause at most 3 changes in an amortized sense. These observati ons are then used to develop O(n log n) incremental algorithms for the se problems.