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