Proofs with potential
Edward F. Grove, Raimund Seidel · 1993
A potential function is a real-valued function that measures the complexity of the state of an algorithm's progress in solving a problem. We use potential functions to analyze algorithms for problems in four separate areas. We give a very simple algorithm for computing the connected components of a graph in a parallel asynchronous model. We obtain the best competitive ratio known for the Online K-Server Problem. We construct the smallest-depth circuits known for multiplying two positive integers. We analyze a natural implementation of the topological sweep-line method for computing the convex regions into which a set of lines dissect the plane.