I recently implemented kmeans1d—discussed in a prior post—for efficiently performing globally optimal 1D *k*-means clustering. The implementation utilizes the SMAWK algorithm (Aggarwal et al., 1987), which calculates `argmin(`

for each row *i*)*i* of an arbitrary `n × m`

*totally monotone* matrix, in `O(m(1 + lg(n/m)))`

.

I’ve factored out my SMAWK C++ code into the example below. In general, SMAWK works with an *implicitly* defined matrix, utilizing a function that returns a value corresponding to an arbitrary position in the matrix. An *explicitly* defined matrix is used in the example for the purpose of illustration.

The program prints the column indices corresponding to the minimum element of each row in a totally monotone matrix. The matrix is from monge.pdf—a course document that I found online.

**References**

Aggarwal, Alok, Maria M. Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. “Geometric Applications of a Matrix-Searching Algorithm.” Algorithmica 2, no. 1 (November 1, 1987): 195–208.