Power Diagrams

Aurenhammer · 1987 · doi:10.1137/0216006

A power diagram partitions space using weighted sites. Each cell contains the points closer to its site after adjusting for weight. Voronoi diagrams are the special case where all weights are equal. The geometry behind embedding-space ad auctions.

From Voronoi to power diagrams

In a standard Voronoi diagram, each cell contains points nearest to its site. A power diagram adds a weight to each site: the "power distance" from point x to site s with weight w is ||x - s||^2 - w. Higher weight expands a cell. In ad auctions, the weight is the bid.

Scheme

; Power diagram: assign point to nearest site by power distance
; power_distance(x, site, weight) = ||x - site||^2 - weight
; Lower power distance wins

(define (square x) (* x x))

(define (power-distance px py sx sy weight)
  (- (+ (square (- px sx)) (square (- py sy)))
     weight))

; Two sites with different weights (= bids)
(define site-a '(2 3))   ; position
(define weight-a 9)      ; high bid
(define site-b '(8 3))   ; position
(define weight-b 1)      ; low bid

; Test point at (5, 3) — midpoint
(define pa (power-distance 5 3 2 3 weight-a))
(define pb (power-distance 5 3 8 3 weight-b))

(display "Power dist to A: ") (display pa) (newline)
(display "Power dist to B: ") (display pb) (newline)
(display "Point (5,3) assigned to: ")
(display (if (< pa pb) 'A 'B)) (newline)

; Without weights, midpoint would be equidistant
; With weights, A's higher bid captures more territory
(display "\nWithout weights:")
(newline)
(define pa0 (power-distance 5 3 2 3 0))
(define pb0 (power-distance 5 3 8 3 0))
(display "Dist to A: ") (display pa0) (newline)
(display "Dist to B: ") (display pb0) (newline)
(display "Equal? ") (display (= pa0 pb0))

; Power diagram: assign point to nearest site by power distance
; power_distance(x, site, weight) = ||x - site||^2 - weight
; Lower power distance wins

(define (square x) (* x x))

(define (power-distance px py sx sy weight)
  (- (+ (square (- px sx)) (square (- py sy)))
     weight))

; Two sites with different weights (= bids)
(define site-a '(2 3))   ; position
(define weight-a 9)      ; high bid
(define site-b '(8 3))   ; position
(define weight-b 1)      ; low bid

; Test point at (5, 3) — midpoint
(define pa (power-distance 5 3 2 3 weight-a))
(define pb (power-distance 5 3 8 3 weight-b))

(display "Power dist to A: ") (display pa) (newline)
(display "Power dist to B: ") (display pb) (newline)
(display "Point (5,3) assigned to: ")
(display (if (< pa pb) 'A 'B)) (newline)

; Without weights, midpoint would be equidistant
; With weights, A's higher bid captures more territory
(display "\nWithout weights:")
(newline)
(define pa0 (power-distance 5 3 2 3 0))
(define pb0 (power-distance 5 3 8 3 0))
(display "Dist to A: ") (display pa0) (newline)
(display "Dist to B: ") (display pb0) (newline)
(display "Equal? ") (display (= pa0 pb0))

Why this matters for ad auctions

In embedding-space auctions, each advertiser is a site in the embedding space and their bid is the weight. The power diagram determines which advertiser wins for each query embedding. Higher bids expand your territory, but relevance (proximity) still matters. This is the geometric mechanism behind buying space instead of keywords: advertisers compete for regions of the embedding space, and the power diagram draws the boundaries. The keyword tax is the cost of pretending these continuous regions are discrete keyword buckets.

Neighbors

△ Geometry — geom-11: power diagrams and weighted Voronoi
june.kim/power-diagrams-ad-auctions — applying power diagrams to ad targeting
💎 Hajiaghayi 2024 — RAG-based alternative to geometric allocation

Ready for the real thing? Read the paper.

← Milgrom & Weber 1982 · 4 of 8 by june.kim Lahaie & Lubin 2025 · 6 of 8 →