Algoritmo SMAWK

El algoritmo SMAWK es un algoritmo para encontrar el valor mínimo en cada fila de una matriz totalmente monótona definida implícitamente . Recibe su nombre de las iniciales de sus cinco inventores: Peter Shor , Shlomo Moran , Alok Aggarwal, Robert Wilber y Maria Klawe . ^{[ 1 ]}

Para los fines de este algoritmo, una matriz se define como monótona si el valor mínimo de cada fila se encuentra en una columna igual o mayor que el mínimo de la fila anterior. Es totalmente monótona si esta misma propiedad se cumple para cada submatriz (definida por un subconjunto arbitrario de las filas y columnas de la matriz dada). De forma equivalente, una matriz es totalmente monótona si no existe una submatriz de 2×2 cuyos mínimos de fila se encuentren en las esquinas superior derecha e inferior izquierda. Toda matriz de Monge es totalmente monótona, pero no necesariamente a la inversa.

Para el algoritmo SMAWK, la matriz que se va a buscar debe definirse como una función, y esta función se proporciona como entrada al algoritmo (junto con las dimensiones de la matriz). El algoritmo evalúa la función cada vez que necesita conocer el valor de una celda específica de la matriz. Si esta evaluación toma O ( 1 ), entonces, para una matriz con r filas y c columnas, el tiempo de ejecución y el número de evaluaciones de la función son ambos O ( c (1  +  log( r / c ))). Esto es mucho más rápido que el tiempo O ( rc ) de un algoritmo ingenuo que evalúa todas las celdas de la matriz.

La idea básica del algoritmo consiste en seguir una estrategia de poda y búsqueda en la que el problema a resolver se reduce a un único subproblema recursivo del mismo tipo, cuyo tamaño es menor por un factor constante. Para ello, el algoritmo preprocesa la matriz eliminando algunas de sus columnas que no pueden contener un mínimo de fila, utilizando un algoritmo basado en pila similar al del escaneo de Graham y a los algoritmos de búsqueda de valores menores más cercanos . Tras esta fase, el número de columnas restantes será, como máximo, igual al número de filas. A continuación, el algoritmo se llama a sí mismo recursivamente para encontrar los mínimos de las filas pares de la matriz. Finalmente, buscando en las columnas entre las posiciones de los mínimos de filas pares consecutivos, el algoritmo completa los mínimos restantes en las filas impares.

Las principales aplicaciones de este método presentadas en el artículo original de Aggarwal et al. fueron en geometría computacional , en encontrar el punto más alejado de cada punto de un polígono convexo y en encontrar polígonos envolventes óptimos. Investigaciones posteriores encontraron aplicaciones del mismo algoritmo en la división de párrafos en líneas , ^{[ 2 ]} predicción de la estructura secundaria del ARN , ^{[ 3 ]} alineación de secuencias de ADN y proteínas , ^{[ 4 ] [ 5 ]} la construcción de códigos de prefijo , ^{[ 6 ]} y umbralización de imágenes , ^{[ 7 ]} entre otras.