En geometría computacional , el problema de la caja delimitadora más pequeña es el de encontrar la caja delimitadora mínima orientada que encierra un conjunto de puntos. Es un tipo de volumen delimitador . "Más pequeño" puede referirse al volumen , área , perímetro , etc. de la caja.
Es suficiente encontrar la caja envolvente más pequeña para el casco convexo de los objetos en cuestión. Es sencillo encontrar la caja envolvente más pequeña que tenga lados paralelos a los ejes de coordenadas; la parte difícil del problema es determinar la orientación de la caja.
Dos dimensiones
Para el polígono convexo , se conoce un algoritmo de tiempo lineal para el rectángulo circundante de área mínima . Se basa en la observación de que un lado de una caja envolvente de área mínima debe ser colineal con un lado del polígono convexo. [1] Es posible enumerar cajas de este tipo en tiempo lineal con el método llamado calibradores rotativos por Godfried Toussaint en 1983. [2] El mismo método es aplicable para encontrar el rectángulo envolvente de perímetro mínimo . [2]
Tres dimensiones
En 1985, Joseph O'Rourke publicó un algoritmo de tiempo cúbico para encontrar la caja envolvente de volumen mínimo de un conjunto de puntos tridimensionales. El enfoque de O'Rourke utiliza una técnica de calibradores giratorios tridimensionales y se basa en lemas que caracterizan la caja de cierre mínima:
- Deben existir dos caras vecinas de la caja envolvente de menor volumen que contengan ambas un borde del casco convexo del conjunto de puntos. Este criterio se satisface por un solo borde convexo del casco colineal con un borde de la caja, o por dos bordes distintos del casco que se encuentran en caras de caja adyacentes.
- Las otras cuatro caras solo necesitan contener un punto del casco convexo. Una vez más, los puntos que contienen no necesitan ser distintos: un solo punto del casco que se encuentra en la esquina de la caja ya satisface tres de estos cuatro criterios.
En el caso más general, en el que no hay vértices convexos del casco en los bordes de la caja envolvente mínima, al menos 8 puntos convexos del casco deben estar dentro de las caras de la caja: dos extremos de cada uno de los dos bordes y cuatro puntos más, uno para cada una de las cuatro caras de caja restantes. Por el contrario, si el casco convexo consta de 7 o menos vértices, al menos uno de ellos debe estar dentro de un borde de la caja de cierre mínima del casco. [3]
También es posible aproximar el volumen mínimo del cuadro delimitador, dentro de cualquier factor constante mayor que uno, en tiempo lineal . El algoritmo para hacer esto implica encontrar una aproximación al diámetro del conjunto de puntos y usar una caja orientada hacia este diámetro como una aproximación inicial a la caja delimitadora de volumen mínimo. Luego, este cuadro delimitador inicial se divide en una cuadrícula de cubos más pequeños, y los puntos de la cuadrícula cerca del límite del casco convexo de la entrada se utilizan como un conjunto de núcleos , un pequeño conjunto de puntos cuyo cuadro delimitador óptimo se aproxima al cuadro delimitador óptimo del entrada original. Finalmente, se aplica el algoritmo de O'Rourke para encontrar el cuadro delimitador óptimo exacto de este núcleo. [4]
Está disponible una implementación de Matlab del algoritmo. [5]
La caja envolvente mínima del tetraedro regular es un cubo, con una longitud de lado 1 / √ 2 la del tetraedro; por ejemplo, un tetraedro regular con una longitud de lado √ 2 encaja en un cubo unitario , con los vértices del tetraedro en los vértices (0,0,0), (0,1,1), (1,0,1) y ( 1,1,0) del cubo unitario. [6]
Ver también
Referencias
- ^ Freeman, H .; Shapira, R. (1975), "Determinar el rectángulo de revestimiento de área mínima para una curva cerrada arbitraria", Comunicaciones del ACM , 18 : 409–413, doi : 10.1145 / 360881.360919 , MR 0375828.
- ^ a b Toussaint, G. T (1983), "Resolver problemas geométricos con los calibradores giratorios" (PDF) , Proc. MELECON '83, Atenas.
- ^ O'Rourke, Joseph (1985), "Finding minimal enclosing boxes", International Journal of Computer and Information Sciences , 14 (3): 183-199, doi : 10.1007 / BF00991005 , MR 0824371.
- ^ Barequet, Gill; Har-Peled, Sariel (2001), "Aproximación eficiente del cuadro delimitador de volumen mínimo de un conjunto de puntos en tres dimensiones", Journal of Algorithms , 38 (1): 91-109, doi : 10.1006 / jagm.2000.1127 , MR 1810433.
- ^ Melchior, Samuel (2018). "Implementación de Matlab del algoritmo de cuadro delimitador de volumen mínimo" ..
- ↑ O'Rourke (1985) , Fig. 1, p. 186.