Power Diagrams

Wikipedia (Power diagram) · june.kim · CC BY-SA 4.0

A power diagram is a weighted Voronoi diagram. Each site has a weight (think: radius of influence). The cell of a site contains all points where the power distance to that site is smallest. The boundary between two cells is still a hyperplane, but it shifts toward the lighter site. This is the geometry behind ad auctions.

Power of a point

The power of a point x with respect to a circle centered at p with radius r is d(x, p)² - r². If the point is outside the circle, the power is positive. On the circle, zero. Inside, negative. The power equals the squared length of the tangent from x to the circle. When r = 0, power reduces to squared Euclidean distance, and the power diagram becomes the ordinary Voronoi diagram.

Scheme

; Power of a point with respect to a circle
; pow(x, (center, radius)) = d(x, center)^2 - radius^2

(define (dist-sq p q)
  (+ (* (- (car p) (car q)) (- (car p) (car q)))
     (* (- (cadr p) (cadr q)) (- (cadr p) (cadr q)))))

(define (power-of-point x center radius)
  (- (dist-sq x center) (* radius radius)))

; Circle centered at (3, 3) with radius 2
(define center (list 3 3))
(define r 2)

; Test points
(for-each
  (lambda (x)
    (let ((pw (power-of-point x center r)))
      (display "pow(") (display x) (display ") = ")
      (display pw)
      (display (cond ((> pw 0) " (outside)")
                     ((= pw 0) " (on circle)")
                     (else     " (inside)")))
      (newline)))
  (list (list 3 3)    ; center -> -4
        (list 5 3)    ; on circle -> 0
        (list 6 3)    ; outside -> 5
        (list 3 4)))  ; inside -> -3

Power cells

Given weighted sites (p_i, w_i), the power cell of site i is the set of points x where d(x, p_i)² - w_i is minimal. Larger weight means a larger cell. A site with zero weight gets the same cell as in the Voronoi diagram. A site with very large weight dominates nearby territory.

Scheme

; Nearest site by power distance (weighted Voronoi)
; power-dist(x, site_i) = d(x, p_i)^2 - w_i

(define (dist-sq p q)
  (+ (* (- (car p) (car q)) (- (car p) (car q)))
     (* (- (cadr p) (cadr q)) (- (cadr p) (cadr q)))))

(define (power-dist x site)
  (let ((center (car site)) (weight (cdr site)))
    (- (dist-sq x center) weight)))

; Three weighted sites: (center . weight)
(define sites
  (list (cons (list 2 2) 1)    ; light
        (cons (list 6 2) 9)    ; heavy — larger cell
        (cons (list 4 5) 4)))  ; medium

(define (nearest-power x sites)
  (let loop ((best (car sites))
             (best-pw (power-dist x (car sites)))
             (rest (cdr sites)))
    (if (null? rest) best
        (let ((pw (power-dist x (car rest))))
          (if (< pw best-pw)
              (loop (car rest) pw (cdr rest))
              (loop best best-pw (cdr rest)))))))

(for-each
  (lambda (x)
    (let ((s (nearest-power x sites)))
      (display "Query ") (display x)
      (display " -> site at ") (display (car s))
      (display " (w=") (display (cdr s)) (display ")") (newline)))
  (list (list 1 1) (list 4 2) (list 5 1) (list 3 4) (list 7 3)))
; Heavy site (6,2) with w=9 claims more territory

; Nearest site by power distance (weighted Voronoi)
; power-dist(x, site_i) = d(x, p_i)^2 - w_i

(define (dist-sq p q)
  (+ (* (- (car p) (car q)) (- (car p) (car q)))
     (* (- (cadr p) (cadr q)) (- (cadr p) (cadr q)))))

(define (power-dist x site)
  (let ((center (car site)) (weight (cdr site)))
    (- (dist-sq x center) weight)))

; Three weighted sites: (center . weight)
(define sites
  (list (cons (list 2 2) 1)    ; light
        (cons (list 6 2) 9)    ; heavy — larger cell
        (cons (list 4 5) 4)))  ; medium

(define (nearest-power x sites)
  (let loop ((best (car sites))
             (best-pw (power-dist x (car sites)))
             (rest (cdr sites)))
    (if (null? rest) best
        (let ((pw (power-dist x (car rest))))
          (if (< pw best-pw)
              (loop (car rest) pw (cdr rest))
              (loop best best-pw (cdr rest)))))))

(for-each
  (lambda (x)
    (let ((s (nearest-power x sites)))
      (display "Query ") (display x)
      (display " -> site at ") (display (car s))
      (display " (w=") (display (cdr s)) (display ")") (newline)))
  (list (list 1 1) (list 4 2) (list 5 1) (list 3 4) (list 7 3)))
; Heavy site (6,2) with w=9 claims more territory

The boundary shifts toward the lighter site

Between two sites, the power diagram boundary is still a hyperplane (a line in 2D). But unlike Voronoi, it is not the perpendicular bisector. It shifts toward the lighter site. The heavier site pushes the boundary away from itself, claiming more territory. When both weights are equal, you recover the Voronoi boundary.

The geometry of ad auctions

In a second-price ad auction, each bidder has a position (relevance score) and a bid (weight). The winning bidder for a query is the one with the smallest power distance. The bid shifts the boundary: a higher bid captures more query territory, exactly like a heavier site in the power diagram. The price paid is determined by the boundary location, not the bid itself. This is the geometric view of the generalized second-price auction.

Scheme

; Ad auction as power diagram
; Each advertiser: (relevance-vector . bid)
; Power distance to query q: d(q, relevance)^2 - bid
; Winner = smallest power distance = highest "score"

(define (dist-sq p q)
  (+ (* (- (car p) (car q)) (- (car p) (car q)))
     (* (- (cadr p) (cadr q)) (- (cadr p) (cadr q)))))

; Advertisers: ((relevance-x relevance-y) . bid)
(define advertisers
  (list (cons (list 3 5) 2)    ; Advertiser A: relevant to (3,5), bid 2
        (cons (list 7 3) 8)    ; Advertiser B: relevant to (7,3), bid 8
        (cons (list 5 8) 5)))  ; Advertiser C: relevant to (5,8), bid 5

(define (power-score query advertiser)
  ; Lower power = wins (like Voronoi nearest)
  (- (dist-sq query (car advertiser)) (cdr advertiser)))

(define (auction-winner query advertisers)
  (let loop ((best (car advertisers))
             (best-pw (power-score query (car advertisers)))
             (rest (cdr advertisers)))
    (if (null? rest) best
        (let ((pw (power-score query (car rest))))
          (if (< pw best-pw)
              (loop (car rest) pw (cdr rest))
              (loop best best-pw (cdr rest)))))))

(for-each
  (lambda (q)
    (let ((w (auction-winner q advertisers)))
      (display "Query ") (display q) (display " -> ")
      (display "Advertiser at ") (display (car w))
      (display " (bid=") (display (cdr w)) (display ")") (newline)))
  (list (list 3 5) (list 6 3) (list 5 7) (list 4 4)))
; Higher bids push boundaries, claiming more query territory

; Ad auction as power diagram
; Each advertiser: (relevance-vector . bid)
; Power distance to query q: d(q, relevance)^2 - bid
; Winner = smallest power distance = highest "score"

(define (dist-sq p q)
  (+ (* (- (car p) (car q)) (- (car p) (car q)))
     (* (- (cadr p) (cadr q)) (- (cadr p) (cadr q)))))

; Advertisers: ((relevance-x relevance-y) . bid)
(define advertisers
  (list (cons (list 3 5) 2)    ; Advertiser A: relevant to (3,5), bid 2
        (cons (list 7 3) 8)    ; Advertiser B: relevant to (7,3), bid 8
        (cons (list 5 8) 5)))  ; Advertiser C: relevant to (5,8), bid 5

(define (power-score query advertiser)
  ; Lower power = wins (like Voronoi nearest)
  (- (dist-sq query (car advertiser)) (cdr advertiser)))

(define (auction-winner query advertisers)
  (let loop ((best (car advertisers))
             (best-pw (power-score query (car advertisers)))
             (rest (cdr advertisers)))
    (if (null? rest) best
        (let ((pw (power-score query (car rest))))
          (if (< pw best-pw)
              (loop (car rest) pw (cdr rest))
              (loop best best-pw (cdr rest)))))))

(for-each
  (lambda (q)
    (let ((w (auction-winner q advertisers)))
      (display "Query ") (display q) (display " -> ")
      (display "Advertiser at ") (display (car w))
      (display " (bid=") (display (cdr w)) (display ")") (newline)))
  (list (list 3 5) (list 6 3) (list 5 7) (list 4 4)))
; Higher bids push boundaries, claiming more query territory

Neighbors

Geometry chapters

△ Chapter 10 — Delaunay Triangulation
△ Chapter 12 — The Erlangen Program

Cross-references

△ june.kim: Power Diagrams and Ad Auctions
△ Economics Ch.24 — auction theory

Foundations (Wikipedia)

Translation notes

The power diagram boundary formula for two sites p1 (weight w1) and p2 (weight w2) is the locus where d(x,p1)² - w1 = d(x,p2)² - w2. Expanding the squared distances, the quadratic terms cancel, leaving a linear equation: the boundary is a hyperplane. The shift from the Voronoi midpoint is (w2 - w1) / (2 * d(p1, p2)). The ad auction interpretation follows Edelman, Ostrovsky, and Schwarz (2007); the power diagram framing is a geometric restatement of their algebraic result.

← Delaunay Triangulation by june.kim The Erlangen Program →