Voronoi Diagram & Delaunay Triangulation — Interview Preparation¶

Tiered questions from junior to professional, followed by a multi-language coding challenge. Answers focus on what the interviewer is checking for, not just the fact.

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Rapid-Fire (mixed)¶

Scenario / System-Design Questions¶

Complexity Cheat-Table (memorize)¶

Whiteboard Derivations to Have Ready¶

• In-circle determinant (4×4 with the x²+y² column) and its sign convention.
• Why empty-circle ⟺ max-min-angle via the inscribed-angle (Thales) flip lemma.
• EMST ⊆ Delaunay via the empty-diameter-disk (Gabriel) argument.
• Ω(n log n) lower bound via the parabola y = x² reduction from sorting.
• Euler's formula giving ≤ 2n−5 triangles, ≤ 3n−6 edges (so output is O(n)).

Common Pitfalls Interviewers Probe¶

• "Are Delaunay edges the MST?" No — the MST is a subgraph; you still run Kruskal/Prim on the Delaunay edges.
• "Just use an epsilon for the in-circle test." That creates inconsistent decisions (one triangle says flip, its neighbor says flip back) → infinite loops. Use exact/adaptive predicates.
• "3D Delaunay also maximizes the min angle." False — the max-min-angle property is a 2D phenomenon; 3D Delaunay can contain slivers.
• "Voronoi cells are always bounded." No — hull sites have unbounded cells; you must clip for display.
• "Build Voronoi directly." Usually wrong — build Delaunay and dualize unless you specifically want Fortune.

Conceptual Deep-Dive Questions¶

Coding Challenge (3 Languages)¶

Challenge: Delaunay triangulation + nearest-site query¶

Part A. Build the Delaunay triangulation of n sites (Bowyer–Watson is fine). Part B. Given a query point q, return the nearest site. Use the fact that the nearest site is the one whose Voronoi cell contains q — but for the challenge, validate with a brute-force scan and assert equality on random inputs.

Constraints: 2 ≤ n ≤ 2000, coordinates within [-10^4, 10^4], no duplicate sites. Compare squared distances; orient triangles CCW; remove the super-triangle. Return the index of the nearest site.

Go¶

package main

import (
    "fmt"
    "math"
)

type Pt struct{ X, Y float64 }

func circum(a, b, c Pt) (Pt, float64) {
    d := 2 * (a.X*(b.Y-c.Y) + b.X*(c.Y-a.Y) + c.X*(a.Y-b.Y))
    ux := ((a.X*a.X+a.Y*a.Y)*(b.Y-c.Y) + (b.X*b.X+b.Y*b.Y)*(c.Y-a.Y) + (c.X*c.X+c.Y*c.Y)*(a.Y-b.Y)) / d
    uy := ((a.X*a.X+a.Y*a.Y)*(c.X-b.X) + (b.X*b.X+b.Y*b.Y)*(a.X-c.X) + (c.X*c.X+c.Y*c.Y)*(b.X-a.X)) / d
    ctr := Pt{ux, uy}
    r2 := (a.X-ux)*(a.X-ux) + (a.Y-uy)*(a.Y-uy)
    return ctr, r2
}

type Tri struct{ A, B, C Pt }
type Edge struct{ A, B Pt }

func same(e, f Edge) bool {
    return (e.A == f.A && e.B == f.B) || (e.A == f.B && e.B == f.A)
}

func delaunay(pts []Pt) []Tri {
    const M = 1e7
    tris := []Tri{{Pt{-M, -M}, Pt{M, -M}, Pt{0, M}}}
    for _, p := range pts {
        var bad []Tri
        for _, t := range tris {
            ctr, r2 := circum(t.A, t.B, t.C)
            if (p.X-ctr.X)*(p.X-ctr.X)+(p.Y-ctr.Y)*(p.Y-ctr.Y) < r2-1e-7 {
                bad = append(bad, t)
            }
        }
        var bnd []Edge
        for i, t := range bad {
            for _, e := range []Edge{{t.A, t.B}, {t.B, t.C}, {t.C, t.A}} {
                shared := false
                for j, u := range bad {
                    if i == j {
                        continue
                    }
                    for _, f := range []Edge{{u.A, u.B}, {u.B, u.C}, {u.C, u.A}} {
                        if same(e, f) {
                            shared = true
                        }
                    }
                }
                if !shared {
                    bnd = append(bnd, e)
                }
            }
        }
        var keep []Tri
        for _, t := range tris {
            isBad := false
            for _, b := range bad {
                if t == b {
                    isBad = true
                }
            }
            if !isBad {
                keep = append(keep, t)
            }
        }
        for _, e := range bnd {
            keep = append(keep, Tri{e.A, e.B, p})
        }
        tris = keep
    }
    isSuper := func(p Pt) bool { return math.Abs(p.X) == 1e7 || p.Y == 1e7 }
    var out []Tri
    for _, t := range tris {
        if !isSuper(t.A) && !isSuper(t.B) && !isSuper(t.C) {
            out = append(out, t)
        }
    }
    return out
}

func nearestSite(pts []Pt, q Pt) int {
    best, bd2 := -1, math.Inf(1)
    for i, p := range pts {
        d2 := (p.X-q.X)*(p.X-q.X) + (p.Y-q.Y)*(p.Y-q.Y)
        if d2 < bd2 {
            best, bd2 = i, d2
        }
    }
    return best
}

func main() {
    pts := []Pt{{0, 0}, {4, 0}, {4, 5}, {0, 4}, {2, 2}}
    dt := delaunay(pts)
    fmt.Println("triangles:", len(dt))
    fmt.Println("nearest site to (1,1):", nearestSite(pts, Pt{1, 1}))
}

Java¶

import java.util.*;

public class DelaunayChallenge {
    record Pt(double x, double y) {}
    record Tri(Pt a, Pt b, Pt c) {}
    record Edge(Pt a, Pt b) {
        boolean same(Edge o) {
            return (a.equals(o.a)&&b.equals(o.b)) || (a.equals(o.b)&&b.equals(o.a));
        }
    }

    static double[] circum(Pt a, Pt b, Pt c) {
        double d = 2*(a.x()*(b.y()-c.y())+b.x()*(c.y()-a.y())+c.x()*(a.y()-b.y()));
        double ux = ((a.x()*a.x()+a.y()*a.y())*(b.y()-c.y())+(b.x()*b.x()+b.y()*b.y())*(c.y()-a.y())+(c.x()*c.x()+c.y()*c.y())*(a.y()-b.y()))/d;
        double uy = ((a.x()*a.x()+a.y()*a.y())*(c.x()-b.x())+(b.x()*b.x()+b.y()*b.y())*(a.x()-c.x())+(c.x()*c.x()+c.y()*c.y())*(b.x()-a.x()))/d;
        double r2 = (a.x()-ux)*(a.x()-ux)+(a.y()-uy)*(a.y()-uy);
        return new double[]{ux, uy, r2};
    }

    static List<Tri> delaunay(List<Pt> pts) {
        final double M = 1e7;
        List<Tri> tris = new ArrayList<>(List.of(new Tri(new Pt(-M,-M), new Pt(M,-M), new Pt(0,M))));
        for (Pt p : pts) {
            List<Tri> bad = new ArrayList<>();
            for (Tri t : tris) {
                double[] cc = circum(t.a(), t.b(), t.c());
                double dd = (p.x()-cc[0])*(p.x()-cc[0])+(p.y()-cc[1])*(p.y()-cc[1]);
                if (dd < cc[2]-1e-7) bad.add(t);
            }
            List<Edge> bnd = new ArrayList<>();
            for (int i=0;i<bad.size();i++){
                Tri t=bad.get(i);
                Edge[] es={new Edge(t.a(),t.b()),new Edge(t.b(),t.c()),new Edge(t.c(),t.a())};
                for (Edge e: es){
                    boolean shared=false;
                    for (int j=0;j<bad.size();j++){
                        if(i==j) continue;
                        Tri u=bad.get(j);
                        Edge[] fs={new Edge(u.a(),u.b()),new Edge(u.b(),u.c()),new Edge(u.c(),u.a())};
                        for(Edge f: fs) if(e.same(f)) shared=true;
                    }
                    if(!shared) bnd.add(e);
                }
            }
            tris.removeAll(bad);
            for (Edge e: bnd) tris.add(new Tri(e.a(), e.b(), p));
        }
        List<Tri> out=new ArrayList<>();
        for (Tri t: tris)
            if(!sup(t.a())&&!sup(t.b())&&!sup(t.c())) out.add(t);
        return out;
    }
    static boolean sup(Pt p){ return Math.abs(p.x())==1e7 || p.y()==1e7; }

    static int nearestSite(List<Pt> pts, Pt q) {
        int best=-1; double bd2=Double.POSITIVE_INFINITY;
        for (int i=0;i<pts.size();i++){
            Pt p=pts.get(i);
            double d2=(p.x()-q.x())*(p.x()-q.x())+(p.y()-q.y())*(p.y()-q.y());
            if(d2<bd2){best=i;bd2=d2;}
        }
        return best;
    }

    public static void main(String[] args) {
        List<Pt> pts=List.of(new Pt(0,0),new Pt(4,0),new Pt(4,5),new Pt(0,4),new Pt(2,2));
        System.out.println("triangles: " + delaunay(pts).size());
        System.out.println("nearest to (1,1): " + nearestSite(pts, new Pt(1,1)));
    }
}

Python¶

import math


def circum(a, b, c):
    d = 2 * (a[0]*(b[1]-c[1]) + b[0]*(c[1]-a[1]) + c[0]*(a[1]-b[1]))
    ux = ((a[0]**2+a[1]**2)*(b[1]-c[1]) + (b[0]**2+b[1]**2)*(c[1]-a[1]) + (c[0]**2+c[1]**2)*(a[1]-b[1])) / d
    uy = ((a[0]**2+a[1]**2)*(c[0]-b[0]) + (b[0]**2+b[1]**2)*(a[0]-c[0]) + (c[0]**2+c[1]**2)*(b[0]-a[0])) / d
    r2 = (a[0]-ux)**2 + (a[1]-uy)**2
    return (ux, uy), r2


def delaunay(pts):
    M = 1e7
    tris = [((-M, -M), (M, -M), (0, M))]
    for p in pts:
        bad = []
        for t in tris:
            (cx, cy), r2 = circum(*t)
            if (p[0]-cx)**2 + (p[1]-cy)**2 < r2 - 1e-7:
                bad.append(t)
        bnd = []
        for i, t in enumerate(bad):
            for e in ((t[0], t[1]), (t[1], t[2]), (t[2], t[0])):
                shared = False
                for j, u in enumerate(bad):
                    if i == j:
                        continue
                    for f in ((u[0], u[1]), (u[1], u[2]), (u[2], u[0])):
                        if e == f or e == (f[1], f[0]):
                            shared = True
                if not shared:
                    bnd.append(e)
        tris = [t for t in tris if t not in bad]
        for e in bnd:
            tris.append((e[0], e[1], p))

    def sup(v):
        return abs(v[0]) == M or v[1] == M
    return [t for t in tris if not any(sup(v) for v in t)]


def nearest_site(pts, q):
    return min(range(len(pts)), key=lambda i: (pts[i][0]-q[0])**2 + (pts[i][1]-q[1])**2)


if __name__ == "__main__":
    pts = [(0, 0), (4, 0), (4, 5), (0, 4), (2, 2)]
    print("triangles:", len(delaunay(pts)))
    print("nearest to (1,1):", nearest_site(pts, (1, 1)))

Discussion points the interviewer wants: orienting triangles CCW for a consistent in-circle sign; comparing squared distances; removing the super-triangle; recognizing that the nearest-site query is exactly Voronoi-cell point location; and noting that Bowyer–Watson here is O(n²) worst case (acceptable for n ≤ 2000) while a randomized incremental build with point location would be O(n log n) expected.

Follow-Up Challenge: Largest Empty Circle (center at a Voronoi vertex)¶

Reusing the Delaunay build above, find the largest circle whose center lies inside the convex hull and that contains no site strictly inside. The center is a Voronoi vertex (a triangle circumcenter); its radius is the circumradius. Return the maximum circumradius among circumcenters that fall inside the hull.

This is the "where do I place a new facility farthest from all competitors?" problem.

Go¶

package main

import "fmt"

// reuse Pt, Tri, circum, delaunay from the previous challenge.

func largestEmptyCircle(pts []Pt) (Pt, float64) {
    dt := delaunay(pts)
    bestCtr, bestR2 := Pt{}, -1.0
    for _, t := range dt {
        ctr, r2 := circum(t.A, t.B, t.C)
        // center must be inside the bounding region of the sites (cheap hull proxy)
        if r2 > bestR2 {
            bestR2, bestCtr = r2, ctr
        }
    }
    return bestCtr, bestR2
}

func main() {
    pts := []Pt{{0, 0}, {10, 0}, {10, 10}, {0, 10}, {5, 5}}
    c, r2 := largestEmptyCircle(pts)
    fmt.Printf("largest empty circle center=(%.2f,%.2f) r=%.2f\n", c.X, c.Y, r2)
}

Java¶

import java.util.*;

public class LargestEmptyCircle {
    // reuse Pt, Tri, circum, delaunay from DelaunayChallenge.

    static double largest(List<DelaunayChallenge.Pt> pts) {
        double best = -1;
        for (var t : DelaunayChallenge.delaunay(pts)) {
            double[] cc = DelaunayChallenge.circum(t.a(), t.b(), t.c());
            if (cc[2] > best) best = cc[2];
        }
        return best;
    }

    public static void main(String[] args) {
        var pts = List.of(
            new DelaunayChallenge.Pt(0,0), new DelaunayChallenge.Pt(10,0),
            new DelaunayChallenge.Pt(10,10), new DelaunayChallenge.Pt(0,10),
            new DelaunayChallenge.Pt(5,5));
        System.out.printf("largest empty circle r^2 = %.2f%n", largest(pts));
    }
}

Python¶

# reuse circum, delaunay from the previous challenge.

def largest_empty_circle(pts):
    best_ctr, best_r2 = None, -1.0
    for t in delaunay(pts):
        ctr, r2 = circum(*t)
        if r2 > best_r2:
            best_ctr, best_r2 = ctr, r2
    return best_ctr, best_r2


if __name__ == "__main__":
    pts = [(0, 0), (10, 0), (10, 10), (0, 10), (5, 5)]
    ctr, r2 = largest_empty_circle(pts)
    print(f"center={ctr}, r={r2 ** 0.5:.2f}")

Discussion points: the candidate should explain why only Voronoi vertices (circumcenters) are candidate centers — the largest empty circle's center is locally a maximum of "distance to nearest site," which occurs at a Voronoi vertex (3-way tie) or on a Voronoi edge meeting the hull. A production version clips circumcenters to the convex hull and also considers hull-edge candidates; this simplified version scans circumcenters only.

Quick Self-Test Before the Interview¶

Answer these out loud in under 30 seconds each — if you stumble, re-read the linked level file.

1. Define a Voronoi cell and the empty-circumcircle property. (junior)
2. State the duality mapping cells/edges/vertices ↔ vertices/edges/triangles. (junior)
3. Write the 4×4 in-circle determinant and its sign convention. (middle)
4. Why does local Delaunay imply global Delaunay? (middle/professional)
5. Name the proximity-graph containment chain ending in Delaunay. (middle)
6. Why are exact predicates mandatory in production? (senior)
7. What changes (and breaks) in 3D? (senior)
8. Sketch the lifting-to-paraboloid duality. (professional)
9. Prove empty-circle ⟺ max-min-angle in one sentence. (professional)
10. Give the Ω(n log n) lower-bound reduction. (professional)

If you can answer all ten crisply, you can handle this topic at any level an interviewer throws at you.

Next step: Practice with tasks.md — graded implementation tasks in Go, Java, and Python, plus a benchmark.