Improved algorithms for discs and balls using power diagrams

F. Aurenhammer

Abstract:

The properties of a particular generalization of Voronoi diagrams called power diagrams are exploited to obtain new and improved algorithms for union, intersection, and measure problems for discs and balls.

Reference: F. Aurenhammer. Improved algorithms for discs and balls using power diagrams. Journal of Algorithms, 9(2):151-161, 1988. [IIG-Report-Series 209, TU Graz, Austria, 1985].