|
Abstract : |
Abstract: The existing O(n log n) algo rithms for nding the convex hulls of circles and the lower envelope of parabolas follow the di vide-and-conquer paradigm. The diOEculty with developing incremental algorithms for these prob lems is that the introduction of a new circle or parabola can cause \Theta(n) structural changes, lead ing to \Theta(n 2) total structural changes during the running of the algorithm. In this note we examine the geometry of these problems and show that, if the circles or parabolas are rst sorted by ap propriate parameters before constructing the con vex hull or lower envelope incrementally, then each new addition may cause at most 3 changes in an amortized sense. These observations are then used to develop O(n log n) incremental algorithms for these problems., |
