A cada milissegundo em que caminhamos por uma cidade com um smartphone no bolso, protocolos sem fio avaliam qual estação rádio-base oferece o menor caminho de sinal e executam transferências (handovers) invisíveis. Quando uma chamada de emergência é feita, os sistemas de despacho dividem instantaneamente a malha viária para determinar qual ambulância ou hospital pode alcançar o paciente no tempo mínimo. E em toda a natureza — dos padrões reticulados das girafas, nervuras das asas de libélulas e colunas basálticas da Calçada dos Gigantes até a teia cósmica de superaglomerados de galáxias cercando imensos vazios intergalácticos — a matéria se auto-organiza em mosaicos poligonais surpreendentemente semelhantes.
Por trás de todos esses fenômenos na epidemiologia espacial, planejamento urbano, redes celulares 5G, geração de malhas para o Método dos Elementos Finitos (MEF), física do estado sólido e morfogênese biológica está a estrutura dual mais fundamental da geometria computacional: o Diagrama de Voronoi e seu grafo dual planar, a Triangulação de Delaunay.
1. O surto de cólera da Broad Street em Londres (1854) e o nascimento das fronteiras invisíveis
No final de agosto de 1854, um devastador surto de cólera atingiu o distrito do Soho, em Londres, ao redor da Broad Street, matando mais de 500 moradores em dez dias (616 no total). Enquanto a medicina oficial defendia a teoria miasmática (transmissão pelo ar fétido), o médico Dr. John Snow (1813–1858) observou que os sintomas atacavam primeiro o trato gastrointestinal e postulou que a cólera era transmitida por água potável contaminada.
Snow mapeou cada óbito como uma barra preta nas ruas do Soho e marcou todas as bombas de água públicas. Para refutar os céticos e explicar por que o abrigo vizinho (Workhouse, com poço próprio) e a cervejaria Lion (onde os trabalhadores bebiam cerveja gratuita e tinham poço profundo) quase não tiveram mortes, Snow traçou uma linha geométrica decisiva: o lugar geométrico dos pontos onde a distância a pé até a bomba da Broad Street era exatamente igual à distância até a bomba pública alternativa mais próxima.
flowchart TD
subgraph Soho["Soho, Londres 1854: Particionamento espacial por proximidade"]
P1["Bomba de água da Broad Street<br/>(Sítio gerador contaminado p₁)"]
P2["Bombas públicas vizinhas<br/>(Sítios geradores limpos p₂, p₃, ..., pₙ)"]
B["Fronteira equidistante / Mediatriz<br/>d(x, p₁) = min_{j≠1} d(x, pⱼ)"]
C1["Célula de Voronoi V(p₁) da Broad Street<br/>(Concentra >90% das mortes por cólera)"]
C2["Células vizinhas V(pⱼ)<br/>(Queda drástica na mortalidade)"]
end
P1 --> B
P2 --> B
B -->|"d(x, p₁) < d(x, pⱼ)"| C1
B -->|"d(x, p₁) > d(x, pⱼ)"| C2
Esse polígono — a célula de Voronoi da bomba da Broad Street — englobava mais de 90% de todas as mortes por cólera! Com a remoção da alavanca da bomba em 8 de setembro de 1854, a epidemia cessou imediatamente. Esse conceito geométrico foi redescoberto de forma independente por René Descartes (1644) em seus vórtices cósmicos (Principia Philosophiae), Peter Gustav Lejeune Dirichlet (1850) em formas quadráticas (domínios de Dirichlet ou células de Wigner-Seitz), Georgy Voronoi (1908) em dimensões arbitrárias $\mathbb{R}^d$, e Alfred H. Thiessen (1911) na meteorologia.
2. Definição matemática e complexidade linear do Diagrama de Voronoi $\text{Vor}(P)$
2.1 Interseção de semiplanos fechados e convexidade
Seja $P = \{p_1, p_2, \dots, p_n\} \subset \mathbb{R}^2$ ($n \ge 3$) um conjunto finito de $n$ pontos distintos (chamados sítios ou geradores) no plano euclidiano. Para dois sítios distintos $p_i, p_j \in P$ ($i \ne j$), a mediatriz $B(p_i, p_j) = \{x \in \mathbb{R}^2 \mid \|x - p_i\|_2 = \|x - p_j\|_2\}$ divide o plano em dois semiplanos fechados. O semiplano de dominância $H(p_i, p_j)$ é:
$$H(p_i, p_j) = \left\{ x \in \mathbb{R}^2 \;\middle|\; \|x - p_i\|_2 \le \|x - p_j\|_2 \right\} = \left\{ x \in \mathbb{R}^2 \;\middle|\; 2(p_j - p_i)^\top x \le \|p_j\|_2^2 - \|p_i\|_2^2 \right\}$$A Célula de Voronoi $\mathcal{V}(p_i)$ associada ao sítio $p_i$ é a interseção dos $n-1$ semiplanos fechados em relação a todos os outros sítios $p_j$ ($j \ne i$):
$$\mathcal{V}(p_i) = \left\{ x \in \mathbb{R}^2 \;\middle|\; \|x - p_i\|_2 \le \|x - p_j\|_2 \;\;\forall j \ne i \right\} = \bigcap_{j \ne i} H(p_i, p_j)$$Como a interseção de conjuntos convexos é convexa, toda célula de Voronoi euclidiana $\mathcal{V}(p_i)$ é um polígono convexo (limitado ou ilimitado). Além disso, $\mathcal{V}(p_i)$ é ilimitada se e somente se $p_i$ pertence à fronteira do fecho convexo $\text{CH}(P)$.
2.2 Prova da complexidade linear pela fórmula de Euler: $V \le 2n - 5$, $E \le 3n - 6$
Embora existam $\binom{n}{2} = \Theta(n^2)$ pares de sítios, o número de vértices $V$ e arestas $E$ de $\text{Vor}(P)$ é estritamente linear em $n$. 【Demonstração】: Compactificamos $\mathbb{R}^2$ na esfera topológica $\mathbb{S}^2$ adicionando um vértice no infinito $v_\infty$ ao qual se conectam todas as semirretas ilimitadas. Obtemos um grafo planar conexo $G' = (V', E', F')$ com $V' = V + 1$ vértices, $E' = E$ arestas e $F' = n$ faces. Pela Fórmula de Euler $V' - E' + F' = 2$:
$$(V + 1) - E + n = 2 \iff E = V + n - 1$$Como cada vértice finito de Voronoi e $v_\infty$ encontram pelo menos 3 células, o grau de cada um dos $V + 1$ vértices satisfaz $\deg(v) \ge 3$. Pelo lema do aperto de mãos:
$$2E = \sum_{v \in V \cup \{v_\infty\}} \deg(v) \ge 3(V + 1) \implies V \le \frac{2}{3}E - 1$$Substituindo em $E = V + n - 1$, obtemos $E \le 3n - 6$ e $V \le 2n - 5$. Como cada aresta é compartilhada por exatamente duas células, o número médio de arestas por célula de Voronoi é:
$$\bar{k} = \frac{2E}{n} \le \frac{2(3n - 6)}{n} = 6 - \frac{12}{n} < 6$$Independentemente de quantos milhões de sítios existam no plano, uma célula de Voronoi tem em média estritamente menos de 6 lados!
| Variante de Voronoi | Função de distância $d(x, p_i)$ | Geometria da bissetriz | Convexidade e topologia | Tamanho (pior caso) | Aplicações científicas e de engenharia |
|---|---|---|---|---|---|
| Euclidiana padrão ($L_2$) | $\|x - p_i\|_2$ | Linha reta (mediatriz) | Sempre convexa e conexa | $\Theta(n)$ | Emergências médicas, meteorologia (Thiessen), vizinho mais próximo |
| Manhattan ($L_1$) | $\|x_1 - x_i\| + \|x_2 - y_i\|$ | Polilinha horizontal, vertical e $\pm 45^\circ$ | Estrelada (não convexa) | $\Theta(n)$ | Logística urbana em ruas ortogonais, roteamento VLSI |
| Chebyshev ($L_\infty$) | $\max(\|x_1 - x_i\|, \|x_2 - y_i\|)$ | Polilinha horizontal, vertical e $\pm 45^\circ$ | Estrelada | $\Theta(n)$ | Pontes rolantes automatizadas, planejamento robótico |
| Ponderado aditivo (AW) | $\|x - p_i\|_2 - w_i$ | Arcos de hipérbole | Estrelada e conexa | $\Theta(n)$ | Crescimento cristalino assíncrono (Johnson-Mehl), localização TDOA |
| Ponderado multiplicativo | $\|x - p_i\|_2 / w_i$ | Arcos circulares (Círculos de Apolônio) | Não convexa, pode desconectar | $\Theta(n^2)$ | Células 5G heterogêneas, áreas de influência comercial |
| Diagrama de potência (Laguerre) | $\|x - p_i\|_2^2 - r_i^2$ | Linha reta (eixo radical) | Sempre convexa (pode ser vazia) | $\Theta(n)$ | Policristais, física de espumas, Transporte Ótimo (OT) |
3. O grafo dual: Triangulação de Delaunay $\text{DT}(P)$ e os três teoremas de equivalência
Em 1934, o matemático russo Boris Delaunay (Delone) definiu o grafo dual planar de $\text{Vor}(P)$ conectando dois sítios $p_i, p_j \in P$ por um segmento se e somente se suas células $\mathcal{V}(p_i)$ e $\mathcal{V}(p_j)$ compartilham uma aresta de Voronoi. Em posição geral (sem quatro pontos cocíclicos), isso produz a Triangulação de Delaunay $\text{DT}(P)$, caracterizada por três teoremas equivalentes:
- Propriedade do círculo circunscrito vazio (Empty Circumcircle Property): Uma triangulação $\mathcal{T}$ é de Delaunay se e somente se o círculo circunscrito $C(\triangle p_i p_j p_k)$ de cada triângulo não contém nenhum outro sítio $p_l \in P$ em seu interior estrito (seu circuncentro é exatamente o vértice de Voronoi dual). Algebricamente, verifica-se pelo determinante $4 \times 4$ $\text{InCircle}(p_i, p_j, p_k, p_l) > 0$.
- Otimalidade Max-Min de ângulos (Sibson 1978 e inversão de arestas de Lawson 1972): No Método dos Elementos Finitos (MEF), triângulos degenerados (sliver triangles) degradam o número de condição $\kappa(K) \propto 1/\sin(\theta_{\min})$ da matriz de rigidez. Entre todas as triangulações possíveis de $P$, $\text{DT}(P)$ maximiza lexicograficamente o vetor ordenado de ângulos internos $\alpha(\mathcal{T})$, maximizando em particular o menor ângulo $\theta_{\min}$! O algoritmo de Lawson (Edge Flip) inverte iterativamente qualquer diagonal que viole a condição do círculo vazio e converge em no máximo $O(n^2)$ inversões.
- Levantamento ao paraboloide 3D (Edelsbrunner & Seidel 1986): Projetando verticalmente cada ponto 2D $(x, y)$ sobre o paraboloide de revolução $\mathcal{P}: z = x^2 + y^2$ em $\mathbb{R}^3$ via $\Phi(x, y) = (x, y, x^2 + y^2)$, a equação de um círculo $(x-a)^2 + (y-b)^2 = R^2$ transforma-se em um plano 3D $z = 2ax + 2by - (a^2 + b^2 - R^2)$. Portanto, a Triangulação de Delaunay $\text{DT}(P)$ é exatamente a projeção vertical no plano $xy$ do fecho convexo inferior (Lower Convex Hull) da nuvem de pontos levantada $\Phi(P)$ em $\mathbb{R}^3$!
4. Algoritmo de linha de varredura e «linha de praia» de Steven Fortune (1986) em $\Theta(n \log n)$
Uma varredura plana ingênua falha porque um ponto acima da linha de varredura $\ell: y = y_{\text{sweep}}$ pode estar mais próximo de um sítio ainda não visitado abaixo de $\ell$. Em 1986, Steven Fortune resolveu esse paradoxo mantendo a linha de praia (Beach Line): a envoltória inferior das parábolas com foco em cada sítio visitado $p_i = (x_i, y_i)$ ($y_i > y_{\text{sweep}}$) e diretriz $\ell$:
$$y = \frac{(x - x_i)^2}{2(y_i - y_{\text{sweep}})} + \frac{y_i + y_{\text{sweep}}}{2}$$Os pontos de quebra (breakpoints) entre dois arcos parabólicos adjacentes são equidistantes de ambos os focos e da diretriz, traçando exatamente as arestas de Voronoi à medida que $\ell$ desce. Usando uma árvore binária de busca balanceada (com no máximo $2n-1$ arcos) e uma fila de prioridade para processar $n$ eventos de sítio (Site Events) e no máximo $2n-5$ eventos de círculo (Circle Events, colapso de um arco no ponto mais baixo de um círculo circunscrito $y_{\text{sweep}} = y_c - R$ criando um vértice de Voronoi), o algoritmo atinge o tempo ótimo $\Theta(n \log n)$ e espaço $\Theta(n)$.
5. Relaxamento de Lloyd e Tesselagens de Voronoi Centroidais (CVT)
Para minimizar a energia de quantização espacial (funcional de $k$-médias) ponderada por uma densidade $\rho(x)$:
$$\mathcal{E}(P, \{\Omega_i\}) = \sum_{i=1}^n \int_{\Omega_i} \|x - p_i\|_2^2 \, \rho(x) \, dx$$as regiões $\Omega_i$ devem ser células de Voronoi $\mathcal{V}(p_i)$ e cada gerador $p_i$ deve coincidir com o centroide (centro de massa) $c_i$ de sua própria célula ($p_i = c_i$), formando uma Tesselagem de Voronoi Centroidal (CVT). O algoritmo de Lloyd (Stuart Lloyd, 1957) move iterativamente cada sítio para o centroide de sua célula ($p_i^{(t+1)} \leftarrow c_i^{(t)}$), reduzindo $\mathcal{E}$ monotonicamente rumo a uma rede hexagonal em favo de mel ótima (teorema de Fejes Tóth, 1953).
Abaixo está uma implementação completa em Python do recorte por semiplanos de Sutherland-Hodgman, integração exata pelo teorema de Green e relaxamento de Lloyd:
| |