Carsten Grimm
Given a set S of n discs in the plane, the furthest-disc Voronoi diagram of S is the subdivision of the plane into regions depending on which disc among S is furthest. In this talk, we present Rappaport's O(n log n) time construction [1] of the furthest-disc Voronoi diagram, which is based on a sweep in three dimensions. For initializing this sweep at the right height, Rappaport constructs and examines the containing hull of S, a generalization of the convex hull of S. We show how to perform the sweep implicitly (i.e., in two dimensions) by reading the furthest-disc Voronoi diagram directly from the containing hull.
[1] David Rappaport, "Computing the Furthest Site Voronoi Diagram for a Set of Discs (Preliminary Report)", Proceedings of the Workshop on Algorithms and Data Structures, 1989, pages 57--66