partición del espacio

En geometría , la partición del espacio es el proceso de dividir un espacio completo (generalmente un espacio euclidiano ) en dos o más subconjuntos disjuntos (véase también partición de un conjunto ). En otras palabras, la partición del espacio divide un espacio en regiones que no se superponen. Cualquier punto del espacio puede entonces identificarse como perteneciente a una sola de estas regiones.

Los sistemas de partición espacial suelen ser jerárquicos , lo que significa que un espacio (o una región del espacio) se divide en varias regiones, y luego el mismo sistema de partición espacial se aplica recursivamente a cada una de las regiones así creadas. Las regiones pueden organizarse en un árbol , llamado árbol de partición espacial .

La mayoría de los sistemas de partición espacial utilizan planos (o, en dimensiones superiores, hiperplanos ) para dividir el espacio: los puntos situados a un lado del plano forman una región, y los puntos situados al otro lado forman otra. Los puntos que se encuentran exactamente sobre el plano suelen asignarse arbitrariamente a uno u otro lado. La partición recursiva del espacio mediante planos de esta forma produce un árbol BSP , una de las formas más comunes de partición espacial.

Los sistemas comunes de partición del espacio incluyen:

• Árboles BSP
• Árboles cuaternarios
• Octrees
• árboles k -d
• contenedores

Supongamos que el espacio euclidiano n-dimensional se particiona por${\displaystyle r}$hiperplanos que son${\displaystyle (n-1)}$-dimensional. ¿Cuál es el número de componentes en la partición? El mayor número de componentes se alcanza cuando los hiperplanos están en posición general , es decir, no hay dos paralelos y no hay tres que tengan la misma intersección. Denotemos este número máximo de componentes por${\displaystyle Comp(n,r)}$. Entonces, se cumple la siguiente relación de recurrencia: ^{[ 4 ] [ 5 ]}

${\displaystyle Comp(n,r)=Comp(n,r-1)+Comp(n-1,r-1)}$

${\displaystyle Comp(0,r)=1}$- Cuando no hay dimensiones, hay un solo punto.

${\displaystyle Comp(n,0)=1}$- Cuando no hay hiperplanos, todo el espacio es un único componente.

Y su solución es:

${\displaystyle Comp(n,r)=\sum _{k=0}^{n}{r \choose k}}$si${\displaystyle r\geq n}$

${\displaystyle Comp(n,r)=2^{r}}$si${\displaystyle r\leq n}$

(considere, por ejemplo,${\displaystyle r}$hiperplanos perpendiculares; cada hiperplano adicional divide cada componente existente en 2).

que está limitado superiormente como:

${\displaystyle Comp(n,r)\leq r^{n}+1}$

• Particionamiento binario del espacio
• Red global discreta
• Partición poligonal
• Mosaico