Generalization of heaps and its applications
Amnon Naamad · 1981
In the complexity theory of algorithms one encounters many problems for which efficient algorithms are known, but one needs to resolve the problems from scratch in order to reflect even a minor change in the data set. This thesis introduces a data structure called heap, which is designed primarily to maintain the solutions of a certain group of problems while the data set is changing over time. Applications of generalized heaps, among other things, include: (1) Maintaining the Voronoi Diagram of a set of points in the plane in linear time. (2) Improving the running time of Dinic's algorithm for the maximum flow problem from O(V('2)E) to O(VE lg('2)V). (3) Improving the running time of Shamos' algorithm for the 2 minimum spanning circles problem from O(n('3) lg n) to O(n('3)). (4) Finding the maximum empty rectangle defined by a set of n points in the plane in O(n 1g('2) n) time (average case). The variety of applications suggests that generalized heaps can also be useful in areas other than graph theory and computational geometry.