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.