VOREXPAND

Definición de Conceptos

La distancia Euclidea entre dos puntos p y q, denotada como dist (p, q), se define como:

Considérese a P como el conjunto {p₁, p₂, ..., p_n} de n puntos distintos en el plano. Estos puntos son llamados sitios (objetos de referencia). Se define el diagrama de Voronoi de P como la subdivisión del plano en n células, una por cada sitio en P. Un punto q pertenece a la célula correspondiente al sitio p_i sí y sólo sí dist(q, p_i) < dist(q, p_j) para cada p_j ÎP con j ¹ i.

Para poder definir formalmente una triangulación de P, definimos primero una subdivisión planar maximal como una subdivisión S en la cual ninguna arista conectando dos vértices puede ser añadida a S sin que deje de ser plana. En otras palabras, ninguna arista que no esté en S corta alguna de las aristas existentes. Una triangulación de P es definida como una subdivisión planar maximal cuyo conjunto de vértices es P.

Siendo P un conjunto de puntos en el plano, y T una triangulación de P. T es una triangulación de Delaunay de P sí y sólo sí la circunferencia circunscrita de cualquier triángulo de T no contiene ningún punto de P en su interior.

El cierre convexo de un conjunto de puntos P en el plano es el polígono convexo que encierra todos los puntos con el perímetro más pequeño.

El grafo del vecino más próximo se define como el grafo que tiene asociado un nodo con cada punto de P y un arco entre ellos si un punto es el más próximo del otro.