algoritmos de cuadro delimitador mínimo

En geometría computacional , el problema de la caja delimitadora mínima consiste en encontrar la caja mínima orientada que encierra un conjunto de puntos. Se trata de un tipo de volumen delimitador . El término "mínima" puede referirse al volumen , área , perímetro , etc. , de la caja.

Basta con hallar la caja que encierre la envoltura convexa de los objetos en cuestión. Resulta sencillo encontrar la caja que tenga lados paralelos a los ejes de coordenadas; la dificultad reside en determinar su orientación.

Para el polígono convexo , se conoce un algoritmo de tiempo lineal para el rectángulo de área mínima que lo encierra . Se basa en la observación de que un lado de una caja de área mínima que lo encierra 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 denominado calibradores rotatorios por Godfried Toussaint en 1983. ^{[ 2 ]} El mismo método es aplicable para encontrar el rectángulo de perímetro mínimo que lo encierra . ^{[ 2 ]} Existe una implementación en C++ del algoritmo que es robusta frente a errores de punto flotante. ^{[ 3 ]}

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 tridimensional. El método de O'Rourke utiliza una técnica de calibradores giratorios tridimensionales y se basa en lemas que caracterizan la caja envolvente mínima:

• Deben existir dos caras contiguas de la caja de menor volumen que contengan una arista de la envoltura convexa del conjunto de puntos. Este criterio se cumple si existe una única arista de la envoltura convexa colineal con una arista de la caja, o si existen dos aristas distintas de la envoltura que se encuentren en caras adyacentes de la caja.
• Las otras cuatro caras solo necesitan contener un punto de la envoltura convexa. De nuevo, los puntos que contienen no tienen por qué ser distintos: un solo punto de la envoltura situado en la esquina de la caja ya cumple tres de estos cuatro criterios.

En el caso más general, donde ningún vértice de la envoltura convexa se encuentra en las aristas de la caja mínima que la contiene, al menos 8 puntos de la envoltura convexa deben estar dentro de las caras de la caja: dos extremos de cada una de las dos aristas y cuatro puntos más, uno por cada una de las cuatro caras restantes de la caja. Por el contrario, si la envoltura convexa consta de 7 o menos vértices, al menos uno de ellos debe estar dentro de una arista de la caja mínima que la contiene. ^{[ 4 ]}

También es posible aproximar el volumen mínimo de la caja delimitadora, con una precisión de un factor constante mayor que uno, en tiempo lineal . El algoritmo para ello consiste en encontrar una aproximación al diámetro del conjunto de puntos y utilizar una caja orientada hacia este diámetro como aproximación inicial a la caja delimitadora de volumen mínimo. A continuación, esta caja delimitadora inicial se divide en una cuadrícula de cubos más pequeños, y los puntos de la cuadrícula cercanos al límite de la envoltura convexa de la entrada se utilizan como un conjunto central , un pequeño conjunto de puntos cuya caja delimitadora óptima se aproxima a la caja delimitadora óptima de la entrada original. Finalmente, se aplica el algoritmo de O'Rourke para encontrar la caja delimitadora óptima exacta de este conjunto central. ^{[ 5 ]}

Existe una implementación del algoritmo en Matlab. ^{[ 6 ]}

La caja mínima que encierra al tetraedro regular es un cubo con lado de longitud${\displaystyle {\frac {1}{\sqrt {2}}}}$la del tetraedro; por ejemplo, un tetraedro regular con longitud de lado${\displaystyle {\sqrt {2}}}$encaja en un cubo unitario , con los vértices del tetraedro situados en los vértices (0,0,0), (0,1,1), (1,0,1) y (1,1,0) del cubo unitario. ^{[ 7 ]}

• Bola de contención más pequeña
• Rectángulo delimitador mínimo