# SMAWK algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/SMAWK_algorithm
> Markdown URL: https://mediated.wiki/source/SMAWK_algorithm.md
> Source: https://en.wikipedia.org/wiki/SMAWK_algorithm
> Source revision: 1305115149
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Combinatorial algorithm}}
The '''SMAWK algorithm''' is an [algorithm](/source/algorithm) for [finding the minimum value](/source/Maximum_and_minimum) in each row of an implicitly defined totally monotone [matrix](/source/Matrix_(mathematics)). It is named after the initials of its five inventors, [Peter Shor](/source/Peter_Shor), [Shlomo Moran](/source/Shlomo_Moran), Alok Aggarwal, Robert Wilber, and [Maria Klawe](/source/Maria_Klawe).<ref name="smawk">{{citation
 | last1 = Aggarwal | first1 = Alok
 | last2 = Klawe | first2 = Maria M. | author2-link = Maria Klawe
 | last3 = Moran | first3 = Shlomo | author3-link = Shlomo Moran
 | last4 = Shor | first4 = Peter | author4-link = Peter Shor
 | last5 = Wilber | first5 = Robert
 | doi = 10.1007/BF01840359
 | issue = 1–4
 | journal = Algorithmica
 | mr = 895444
 | pages = 195–208
 | title = Geometric applications of a matrix-searching algorithm
 | volume = 2
 | year = 1987}}.</ref>

==Input==
For the purposes of this algorithm, a matrix is defined to be monotone if each row's minimum value occurs in a column which is equal to or greater than the column of the previous row's minimum. It is totally monotone if the same property is true for every submatrix (defined by an arbitrary subset of the rows and columns of the given matrix). Equivalently, a matrix is totally monotone if there does not exist a 2×2 submatrix whose row minima are in the top right and bottom left corners. Every [Monge array](/source/Monge_array) is totally monotone, but not necessarily vice versa.

For the SMAWK algorithm, the matrix to be searched should be defined as a function, and this function is given as input to the algorithm (together with the dimensions of the matrix). The algorithm then evaluates the function whenever it needs to know the value of a particular matrix cell.  If this evaluation takes ''O''(''1''), then, for a matrix with ''r'' rows and ''c'' columns, the running time and number of function evaluations are both ''O''(''c''(1&nbsp;+&nbsp;log(''r''/''c''))). This is much faster than the ''O''(''r'' ''c'') time of a naive algorithm that evaluates all matrix cells.

==Method==
The basic idea of the algorithm is to follow a [prune and search](/source/prune_and_search) strategy in which the problem to be solved is reduced to a single [recursive](/source/Recursion_(computer_science)) subproblem of the same type whose size is smaller by a constant factor. To do so, the algorithm first preprocesses the matrix to remove some of its columns that cannot contain a row-minimum, using a [stack](/source/stack_(data_structure))-based algorithm similar to the one in the [Graham scan](/source/Graham_scan) and [all nearest smaller values](/source/all_nearest_smaller_values) algorithms. After this phase of the algorithm, the number of remaining columns will at most equal the number of rows.
Next, the algorithm calls itself recursively to find the row minima of the even-numbered rows of the matrix. Finally, by searching the columns between the positions of consecutive even-row minima, the algorithm fills out the remaining minima in the odd rows.

==Applications==
The main applications of this method presented in the original paper by Aggarwal et al. were in [computational geometry](/source/computational_geometry), in finding the farthest point from each point of a convex polygon, and in finding optimal enclosing polygons. Subsequent research found applications of the same algorithm in [breaking paragraphs into lines](/source/Word_wrap),<ref>{{citation
 | last = Wilber | first = Robert
 | doi = 10.1016/0196-6774(88)90032-6
 | issue = 3
 | journal = Journal of Algorithms
 | mr = 955150
 | pages = 418–425
 | title = The concave least-weight subsequence problem revisited
 | volume = 9
 | year = 1988}}</ref> [RNA](/source/RNA) [secondary structure](/source/Nucleic_acid_secondary_structure) prediction,<ref>{{citation
 | last1 = Larmore | first1 = Lawrence L. | author1-link = Lawrence L. Larmore
 | last2 = Schieber | first2 = Baruch | author2-link = Baruch Schieber
 | doi = 10.1016/0196-6774(91)90016-R
 | issue = 3
 | journal = Journal of Algorithms
 | mr = 1114923
 | pages = 490–515
 | title = On-line dynamic programming with applications to the prediction of RNA secondary structure
 | volume = 12
 | year = 1991}}.</ref> [DNA](/source/DNA) and [protein](/source/protein) [sequence alignment](/source/sequence_alignment),<ref>{{citation
 | last = Russo | first = Luís M. S.
 | doi = 10.1016/j.tcs.2011.12.068
 | journal = Theoretical Computer Science
 | mr = 2887979
 | pages = 30–49
 | title = Monge properties of sequence alignment
 | volume = 423
 | year = 2012| doi-access = free
 }}.</ref><ref>{{citation
 | last1 = Crochemore | first1 = Maxime
 | last2 = Landau | first2 = Gad M.
 | last3 = Ziv-Ukelson | first3 = Michal
 | doi = 10.1137/S0097539702402007
 | issue = 6
 | journal = SIAM Journal on Computing
 | mr = 2034254
 | pages = 1654–1673 (electronic)
 | title = A subquadratic sequence alignment algorithm for unrestricted scoring matrices
 | volume = 32
 | year = 2003| citeseerx = 10.1.1.57.8562}}.</ref> the construction of [prefix code](/source/prefix_code)s,<ref>{{citation
 | last1 = Bradford | first1 = Phil
 | last2 = Golin | first2 = Mordecai J.
 | last3 = Larmore | first3 = Lawrence L. | author3-link = Lawrence L. Larmore
 | last4 = Rytter | first4 = Wojciech | author4-link = Wojciech Rytter
 | doi = 10.1006/jagm.2002.1213
 | issue = 2
 | journal = Journal of Algorithms
 | mr = 1895977
 | pages = 277–303
 | title = Optimal prefix-free codes for unequal letter costs: dynamic programming with the Monge property
 | volume = 42
 | year = 2002| citeseerx = 10.1.1.45.5501
 }}.</ref> and [image thresholding](/source/Thresholding_(image_processing)),<ref>{{citation
 | last1 = Luessi | first1 = M.
 | last2 = Eichmann | first2 = M.
 | last3 = Schuster | first3 = G.M.
 | last4 = Katsaggelos | first4 = A.K.
 | contribution = New results on efficient optimal multilevel image thresholding
 | doi = 10.1109/ICIP.2006.312426
 | pages = 773–776
 | title = IEEE International Conference on Image Processing
 | year = 2006| isbn = 978-1-4244-0480-3
 | citeseerx = 10.1.1.461.663
 }}.</ref> among others.

==References==
{{reflist}}

Category:Combinatorial algorithms
Category:Matrix theory

---
Adapted from the Wikipedia article [SMAWK algorithm](https://en.wikipedia.org/wiki/SMAWK_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/SMAWK_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.