Algoritmos de cuadro delimitador mínimo
En geometría computacional , el problema de la caja envolvente 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 de cierre 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.
Para el polígono convexo , se conoce un algoritmo de tiempo lineal para el rectángulo que lo encierra 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 enfoque denominado calibradores giratorios de Godfried Toussaint en 1983. [2] El mismo enfoque es aplicable para encontrar el rectángulo que las encierra con el perímetro mínimo . [2]
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 envolvente mínima:
En el caso más general, en el que no hay vértices de casco convexo en los bordes de la caja envolvente mínima, se sigue que al menos 8 puntos de casco convexo 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 envolvente 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 un cuadro orientado hacia este diámetro como una aproximación inicial al cuadro delimitador 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 central , un pequeño conjunto de puntos cuyo cuadro delimitador óptimo se aproxima al cuadro delimitador óptimo de la entrada. entrada original. Finalmente, se aplica el algoritmo de O'Rourke para encontrar el cuadro delimitador óptimo exacto de este conjunto básico. [4]
