Partición del espacio

División de un espacio entero en ≥2 subconjuntos disjuntos

En geometría , la partición espacial es el proceso de dividir un espacio entero (normalmente 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 espacial divide un espacio en regiones no superpuestas. De este modo, cualquier punto del espacio puede identificarse como perteneciente exactamente a una de las regiones.

Descripción general

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

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

Usos

En gráficos por computadora

La partición del espacio es particularmente importante en gráficos de computadora , especialmente en el trazado de rayos , donde se utiliza con frecuencia para organizar los objetos en una escena virtual. Una escena típica puede contener millones de polígonos. Realizar una prueba de intersección de rayos y polígonos con cada uno de ellos sería una tarea muy costosa desde el punto de vista computacional.

El almacenamiento de objetos en una estructura de datos con particiones espaciales ( árbol k -d o árbol BSP , por ejemplo) hace que sea fácil y rápido realizar ciertos tipos de consultas de geometría; por ejemplo, para determinar si un rayo interseca un objeto, la partición espacial puede reducir la cantidad de pruebas de intersección a solo unas pocas por rayo primario, lo que produce una complejidad de tiempo logarítmica con respecto a la cantidad de polígonos. ^{[1] [2] [3]}

La partición espacial también se utiliza a menudo en algoritmos de línea de escaneo para eliminar los polígonos del frustum de visualización de la cámara , lo que limita la cantidad de polígonos procesados ​​por la tubería. También se utiliza en la detección de colisiones : determinar si dos objetos están cerca uno del otro puede ser mucho más rápido utilizando la partición espacial.

En el diseño de circuitos integrados

En el diseño de circuitos integrados , un paso importante es la comprobación de las reglas de diseño . Este paso garantiza que el diseño finalizado sea fabricable. La comprobación implica reglas que especifican anchos y espaciados y otros patrones geométricos. Un diseño moderno puede tener miles de millones de polígonos que representan cables y transistores. Una comprobación eficiente depende en gran medida de la consulta de geometría. Por ejemplo, una regla puede especificar que cualquier polígono debe estar al menos a n nanómetros de cualquier otro polígono. Esto se convierte en una consulta de geometría ampliando un polígono en n/2 en todos los lados y consultando para encontrar todos los polígonos que se intersecan.

En teoría de probabilidad y aprendizaje estadístico

El número de componentes de una partición espacial desempeña un papel central en algunos resultados de la teoría de la probabilidad. Véase Función de crecimiento para obtener más detalles.

En geografía y SIG

Son muchos los estudios y aplicaciones donde se segmenta la Realidad Geográfica Espacial mediante criterios hidrológicos , administrativos , matemáticos o muchos otros.

En el contexto de la cartografía y los SIG (sistemas de información geográfica) , es habitual identificar las celdas de la partición mediante códigos estándar . Por ejemplo, el código HUC que identifica cuencas y subcuencas hidrográficas, los códigos ISO 3166-2 que identifican países y sus subdivisiones, o las DGG arbitrarias (cuadrículas globales discretas que identifican cuadrantes o ubicaciones).

Estructuras de datos

Los sistemas comunes de partición de espacios incluyen:

• Árboles BSP
• Árboles cuaternarios
• Octárboles
• árboles k -d
• Contenedores
• Árboles R

Número de componentes

Supongamos que el espacio euclidiano n-dimensional está dividido en hiperplanos que son -dimensionales. ¿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 la posición general , es decir, no hay dos que sean paralelos y no hay tres que tengan la misma intersección. Denotemos este número máximo de componentes por . Entonces, se cumple la siguiente relación de recurrencia: ^{[4] [5]} ${\displaystyle r}$ ${\displaystyle (n-1)}$ ${\displaystyle Comp(n,r)}$

${\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 solo 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}$

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

cuyo límite superior es:

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

Véase también

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

Referencias

1. Tomas Nikodym (2010). "Algoritmo de trazado de rayos para aplicaciones interactivas" (PDF) . Universidad Técnica Checa, FEE .
2. Ingo Wald, William R. Mark; et al. (2007). "Estado del arte en escenas animadas con trazado de rayos". Eurographics . CiteSeerX 10.1.1.108.8495 . 
3. Trazado de rayos: estructuras de datos auxiliares
4. Vapnik, VN; Chervonenkis, A. Ya. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Teoría de la probabilidad y sus aplicaciones . 16 (2): 266. doi :10.1137/1116025.Se trata de una traducción al inglés, realizada por B. Seckler, del artículo ruso: "Sobre la convergencia uniforme de las frecuencias relativas de los acontecimientos con sus probabilidades". Dokl. Akad. Nauk . 181 (4): 781. 1968.La traducción fue reproducida como: Vapnik, VN; Chervonenkis, A. Ya. (2015). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Medidas de complejidad . p. 11. doi :10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
5. Véase también discusiones y explicaciones detalladas sobre el caso n=2 y el caso general. Véase también Winder, RO (1966). "Particiones del espacio N mediante hiperplanos". SIAM Journal on Applied Mathematics . 14 (4): 811–818. doi :10.1137/0114068..