Voronoi Diagrams: Manhattan to Euclidean

---

# 🗺️ Voronoi Diagrams: Manhattan → Euclidean

## Adding an L2 backend to a divide-and-conquer L1 library

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**The Problem** 🤔
- Recap: the L1 (Lee–Wong) pipeline 🧵
- The metric seam and why L2 cannot use it 🚧
- Euclidean Voronoi in one picture 📐

**The Algorithm** ⚙️
- Guibas–Stolfi divide & conquer ✂️
- Quad-edge & the rising bubble 🫧
- Robust predicates 🎯

]
.pull-right[

**From Delaunay to Voronoi** 🎭
- Half-plane clipping 🖼️
- The four figures 📊

**Proof & Tooling** ✅
- Brute-force oracle 🧪
- 500 random trials 🎲
- The live demo 🌐

]

---

## 🧵 Part 1 — Where We Start

---

### 🧭 The L1 Pipeline (recap)

.mermaid[
<pre>
flowchart LR
    A["Sites\n[x,y]"] --> B["sort by x, y"]
    B --> C["recursiveSplit"]
    C --> D["walkMergeLine"]
    D --> E["polygonizeSite"]
    E --> F["toCell DTO\n+ SVG path"]

style A fill:#4caf50
    style B fill:#2196f3
    style C fill:#ff9800
    style D fill:#9c27b0
    style E fill:#f44336
    style F fill:#009688
</pre>
]

> Lee & Wong: split the sites, merge along a staircase, chain bisectors into polygons. 🪜

---

### 📐 The L1 Metric

The Manhattan distance between two points:

$$d_1(p, q) = |p_x - q_x| + |p_y - q_y|$$

The L1 bisector of two sites is **not** a straight line — it is a staircase:

$$B_1(p,q) = \{\, x : d_1(x,p) = d_1(x,q) \,\}$$

> This kinked shape is why L1 cells have "strange protrusions". 🪚

---

### 🧵 The Metric Seam

The refactor bundled the L1-specific pieces into one strategy object:

```javascript
const metric = createL1Metric(width, height);
// { width, height, distance, bisector, isUpward }
```

Every pipeline stage receives `metric`, so the arithmetic is swappable. 🎛️

---

### ❓ The Obvious Question

> If the arithmetic is behind a seam, can we just plug in a **Euclidean** metric?

$$\text{createL1Metric} \;\longrightarrow\; \text{createL2Metric}\;?$$

Tempting... but the answer is **no**. 🚫

---

### 🚧 Why L2 Cannot Plug In

The seam abstracts the *arithmetic*, not the *geometry*. The merge **control flow** is L1-shaped:

.mermaid[
<pre>
flowchart TD
    A["metric.distance"] --> OK["✅ swappable"]
    B["bisector.up flag"] --> NO["❌ L1 only"]
    C["sort points by y (up)\nor x (down)"] --> NO
    D["first border crossed\n= min y-difference"] --> NO
    E["two strokes:\nup from corner, down from corner"] --> NO

style OK fill:#4caf50
    style NO fill:#f44336
    style A fill:#2196f3
    style B fill:#ff9800
    style C fill:#ff9800
    style D fill:#ff9800
    style E fill:#ff9800
</pre>
]

---

### 🔬 The Evidence

An L1 bisector carries a binary **up** flag and is walked by y-order:

```javascript
// bisector.js — trimBisector
target.points.sort((a, b) => target.up
    ? a[1] - b[1]      // upward: order by y
    : a[0] - b[0]);    // downward: order by x
```

A Euclidean bisector is a single straight line — it has no up/down, and sorting by x or y is meaningless. 🎯

---

### ✅ Decision: A Separate Backend

> The metric seam is right for **L1-like** metrics (e.g. $L_\infty$ is a 45° rotation of $L_1$).
> Euclidean needs a *different algorithm*, not a different distance. 🧱

So L2 becomes its own divide-and-conquer backend, reusing only the low-level geometry and the `toCell` DTO. 🎭

---

### 🧩 The Shared DTO

**DTO** = **Data Transfer Object** — a plain, serializable object that carries data across a boundary, with no behavior. 🎁

The internal `Site` / `Bisector` graph is mutable and full of implementation detail; `cell.js` maps it to a plain result:

```javascript
{ site, polygonPoints, d, neighbors, bisectors }
```

> Both backends emit the **same** DTO — L1 and L2 share the boundary even though their algorithms share almost nothing else. 🎭

---

## 📐 Part 2 — Euclidean Voronoi

---

### ➗ The Euclidean Bisector

The set of points equidistant from two sites is the **perpendicular bisector**:

$$\|x - p\| = \|x - q\| \;\Longleftrightarrow\; 2\,(q - p)\cdot x = \|q\|^2 - \|p\|^2$$

A single straight line — no staircase, no kinks. 📏

---

### 🖼️ Voronoi = Half-Plane Intersection

Each Voronoi cell is the intersection of half-planes, one per other site:

$$V_i \;=\; \bigcap_{j \neq i} \{\, x : \|x - p_i\| \le \|x - p_j\| \,\}$$

Only the **Delaunay neighbours** give non-redundant constraints — so the cell is an $O(\deg)$ object. 🧩

---

### 🔺 Delaunay Duality

.mermaid[
<pre>
graph LR
    subgraph Delaunay
        D1["triangle"] --- D2["triangle"]
    end
    subgraph Voronoi
        V1["circumcenter"] --- V2["circumcenter"]
    end
    D1 -. "dual" .-> V1
    D2 -. "dual" .-> V2

style D1 fill:#2196f3
    style D2 fill:#2196f3
    style V1 fill:#9c27b0
    style V2 fill:#9c27b0
</pre>
]

> The Voronoi diagram is the dual of the Delaunay triangulation. Compute one, get the other. 🔄

---

## ✂️ Part 3 — Divide & Conquer (Guibas–Stolfi)

---

### 🪜 The Same Skeleton, A Different Merge

.mermaid[
<pre>
flowchart TD
    S["n sites, sorted by x"] --> L["recurse left"]
    S --> R["recurse right"]
    L --> M["merge"]
    R --> M
    M --> T["Delaunay triangulation"]
    T --> V["Voronoi cells"]

style S fill:#4caf50
    style L fill:#2196f3
    style R fill:#2196f3
    style M fill:#ff9800
    style T fill:#9c27b0
    style V fill:#009688
</pre>
]

> Split and recurse exactly like L1 — but the merge is **lower-common-tangent + rising bubble**, not a staircase walk. 🫧

---

### 🔷 The Quad-Edge

Each undirected edge is four directed records forming a rot cycle:

.mermaid[
<pre>
graph LR
    q0["q0\norig → dest"] --> q1["q1\nrot"]
    q1 --> q2["q2\ndest → orig"]
    q2 --> q3["q3\nrot (dual)"]
    q3 --> q0

style q0 fill:#4caf50
    style q2 fill:#2196f3
    style q1 fill:#ff9800
    style q3 fill:#9c27b0
</pre>
]

Primitives: `makeEdge`, `splice`, `connect`, `deleteEdge`. The primal and the dual live in the same structure. 🧬

---

### 🫧 The Merge

1. Find the **lower common tangent** of the two hulls 🧲
2. Repeatedly pick the next Delaunay edge with the **rising bubble** 🫧
3. Delete any edge whose circumcircle contains the candidate

The predicate that decides is **InCircle**:

$$\text{InCircle}(a,b,c,d) > 0 \;\Longleftrightarrow\; d \text{ lies inside the circumcircle of } abc$$

---

### 🎯 Robustness: Normalise, then Filter

Coordinates are normalised to $[0,1]^2$ so the floating-point determinant is well conditioned:

$$\text{err} = 1.11\times10^{-15}\cdot \text{permanent},\qquad \text{sign} = \begin{cases} + & \det > \text{err} \\ - & \det < -\text{err} \\ 0 & \text{otherwise} \end{cases}$$

Degenerate ties break deterministically on site index — the algorithm always terminates. 🛡️

---

## 🎭 Part 4 — From Delaunay to Voronoi

---

### 🖼️ Half-Plane Clipping

Instead of materialising rays for unbounded cells, clip the **canvas rectangle** by each bisector half-plane:

$$f(x) = \|x - p_i\|^2 - \|x - p_j\|^2 \;\le\; 0$$

Start with the rectangle, clip with Sutherland–Hodgman per Delaunay neighbour, normalise the winding to positive area. ✅

---

### ⚖️ Why Clipping, Not Circumcenter Rays

**Circumcenter dual** 🔺
- Compute every triangle's circumcenter
- Hull edges → unbounded rays
- Must then clip the unbounded cell

]
.pull-right[

**Half-plane clipping** ✂️
- One uniform path for bounded & unbounded
- No rays, no point-at-infinity
- Exactly the canvas-clipped cell

]

> Fewer special cases, fewer bugs. The Delaunay graph still does the hard work. 🧠

---

### ⏱️ Complexity

The divide-and-conquer triangulation is optimal:

$$T(n) = 2\,T(n/2) + O(n) \;=\; O(n \log n)$$

Clipping is $O(\sum \deg) = O(n)$ over the whole diagram. Total: $O(n \log n)$. 🚀

---

## 📊 Part 5 — The Four Figures

---

### 🟦 Figure 1 — L1 (Manhattan) Cells

</p>

> Staircase bisectors → kinked, rectilinear cells. 🪚

---

### 🟦 Figure 2 — L1 Delaunay Graph

</p>

> The dual of the L1 diagram: sites are joined when their cells share a bisector. Dense, because L1 vertices are often degree-4. 🔷

---

### 🟧 Figure 3 — L2 (Euclidean) Cells

</p>

> Straight perpendicular bisectors → convex polygon cells. 📏

---

### 🟧 Figure 4 — L2 Delaunay Graph

</p>

> The divide-and-conquer triangulation that drives the L2 cells. 🔺

---

### 🔍 Side by Side

> Same sites, two metrics, two duals — the whole story in one grid. 🎛️

The four figures above are the library's own output, exported as standalone SVG. 📦

---

## 🧪 Part 6 — Proof & Tooling

---

### 🎯 Brute-Force Oracle

.mermaid[
<pre>
flowchart LR
    G["sample grid\npoints"] --> N["nearest site\n(Euclidean)"]
    G --> C["find containing\ncell polygon"]
    N --> A{"same site?"}
    C --> A
    A -->|yes| P["✅ pass"]
    A -->|no| F["❌ violation"]

style G fill:#4caf50
    style N fill:#2196f3
    style C fill:#ff9800
    style A fill:#9c27b0
    style P fill:#009688
    style F fill:#f44336
</pre>
]

> Independent of how the cells were built — it only checks the defining property. 🧪

---

### 🎲 Verification

| Check | Result |
|:------|:-------|
| `npm test` | **22/22** (9 L1 + 13 L2) |
| L2 oracle, 5 corpora | **pass** ✅ |
| 500 random trials | **0 failures** 🎉 |
| Area partition (Σ cells = canvas) | **pass** 📐 |
| Neighbour reciprocity | **pass** 🔄 |
| `npm run test:diff` | **7 baseline, 0 new** 🐍 |
| `npx gulp` | library + both demos ✅ |

---

### 🧬 Degeneracies Handled

**Input** 🧹
- Duplicate points → dedupe
- Collinear sites → open chain, still correct
- Cocircular sites → deterministic tie-break

]
.pull-right[

**Geometry** 📐
- Unbounded cells → clipped to canvas
- Winding → normalised to positive area
- Robustness → normalised + filtered predicates

]

> The Voronoi diagram is unique even when the triangulation is not. 🎯

---

### 🌐 The Live Demo

.mermaid[
<pre>
flowchart LR
    U["l2.html\n?points=N"] --> B1["generateL1Voronoi"]
    U --> B2["generateL2Voronoi"]
    B1 --> P1["L1 cells\n+ L1 Delaunay"]
    B2 --> P2["L2 cells\n+ L2 Delaunay"]

style U fill:#4caf50
    style B1 fill:#2196f3
    style B2 fill:#ff9800
    style P1 fill:#9c27b0
    style P2 fill:#009688
</pre>
]

> A 2×2 grid: L1 cells, L1 Delaunay, L2 cells, L2 Delaunay — rendered live in the browser. 🖥️

---

### 📦 What Was Added

| File | Role |
|:-----|:-----|
| `src/quadEdge.js` | quad-edge primitives |
| `src/l2Delaunay.js` | predicates + D&C + neighbour graph |
| `src/l2Voronoi.js` | half-plane clipping + `generateL2Voronoi` |
| `tests/l2Oracle.js` | brute-force nearest-site oracle |
| `tests/l2.test.js` | 13 oracle & contract tests |
| `l2main.js` / `l2.html` | the demo |

Zero new runtime dependencies. 🪶

---

### 🧠 Key Takeaways

**Design** 🧩
- A seam is only as good as the geometry it hides
- Swappable arithmetic ≠ swappable algorithm
- Separate backends can share the DTO boundary
- Reuse the *shape*, not the *assumptions*

]
.pull-right[

**Algorithm** ⚙️
- Divide & conquer generalises — the merge does not
- Quad-edge keeps primal and dual together
- Half-plane clipping beats ray bookkeeping
- Normalise before you predicate

]

---

### 📜 The Story So Far

.mermaid[
<pre>
graph LR
    A["L1\nLee–Wong"] --> B["metric seam\n(createL1Metric)"]
    B --> C["L2\nGuibas–Stolfi"]
    C --> D["shared DTO\ntoCell"]
    D --> E["one demo,\nfour figures"]

style A fill:#4caf50
    style B fill:#2196f3
    style C fill:#ff9800
    style D fill:#9c27b0
    style E fill:#009688
</pre>
]

> From one metric to two, without touching the L1 output. 🎉

---

# 🙋 Q&A

**Voronoi Diagrams: Manhattan → Euclidean**

### Questions? Discussion? 💬

---

# 👏 Thank You

## Happy Voronoi Tiling! 🗺️ 🚀

Slides built with Remark.js 🎉 | KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙