A JS port of the ConcaveMinima algorithm from D. Eppstein (http://www.ics.uci.edu/~eppstein/PADS/SMAWK.py)

OnlineConcaveMinima.coffee

class OnlineConcaveMinima
	
	values = []
	indices = [0]
	finished = 0
	
	matrix = (i, j) -> 0
	base = 0
	tentative = 0
	
	constructor: (Matrix, initial) ->
		values = [initial]
		indices = [0]
		matrix = Matrix
	
	value: (index) ->
		@advance() while finished < index
		values[index]
	
	index: (val) ->
		@advance() while finished < val
		indices[val]
	
	advance: () ->
		i = finished + 1
		
		if(i > tentative)
			rows = [base..finished]
			tentative = finished + rows.length
			cols = [finished + 1..tentative]
			minima = @concaveMinima rows, cols, matrix
			for col in cols
				if(col > values.length)
					values.push minima[col][0]
					indices.push minima[col][1]
				else if(minima[col][0] < values[col])
					values[col] = indices[col] = minima[col]
			finished = i
			return
		
		diag = matrix(i - 1, i)
		if(diag < values[i])
			values[i] = diag
			indices[i] = base = i - 1
			tentative = finished = i
			return
		
		if(matrix(i - 1, tentative) >= values[tentative])
			finished = i
			return
		
		base = i - 1
		tentative = finished = i
		return
	
	concaveMinima: (rows, cols, matrix) ->
		return [] if !cols || cols.length == 0
		
		s = []
		for r in rows
			s.pop() while (s.length > 0 && matrix(s[s.length - 1], cols[s.length - 1]) > matrix(r, cols[s.length - 1]) > 0)
			s.push(r) if(s.length != cols.length)
		rows = s
		
		# rows.length = cols.length if rows.length != cols.length

		mCols = []
		mCols.push cols[i] for i in [1...cols.length] by 2
		minima = @concaveMinima rows, mCols, matrix 

		r = 0
		for i in [0...cols.length] by 2
			col = cols[i]
			row = rows[r]
			lastrow = if(i == cols.length - 1) then rows[rows.length - 1] else minima[cols[i + 1]][1]
			pair = [matrix(row, col), row]
			while(row != lastrow)
				row = rows[++r]
				pair1 = [matrix(row, col), row]
				continue if(pair[0] < pair1[0])
				continue if(pair[0] == pair1[0] && pair[1] < pair1[1])
				pair = pair1
			minima[col] = pair
		minima

OnlineConcaveMinima.js

var OnlineConcaveMinima;

OnlineConcaveMinima = (function() {
  var base, finished, indices, matrix, tentative, values;

  values = [];

  indices = [0];

  finished = 0;

  matrix = function(i, j) {
    return 0;
  };

  base = 0;

  tentative = 0;

  function OnlineConcaveMinima(Matrix, initial) {
    values = [initial];
    indices = [0];
    matrix = Matrix;
  }

  OnlineConcaveMinima.prototype.value = function(index) {
    while (finished < index) {
      this.advance();
    }
    return values[index];
  };

  OnlineConcaveMinima.prototype.index = function(val) {
    while (finished < val) {
      this.advance();
    }
    return indices[val];
  };

  OnlineConcaveMinima.prototype.advance = function() {
    var col, cols, diag, i, minima, rows, _i, _j, _k, _len, _ref, _results, _results2;
    i = finished + 1;
    if (i > tentative) {
      rows = (function() {
        _results = [];
        for (var _i = base; base <= finished ? _i <= finished : _i >= finished; base <= finished ? _i++ : _i--){ _results.push(_i); }
        return _results;
      }).apply(this);
      tentative = finished + rows.length;
      cols = (function() {
        _results2 = [];
        for (var _j = _ref = finished + 1; _ref <= tentative ? _j <= tentative : _j >= tentative; _ref <= tentative ? _j++ : _j--){ _results2.push(_j); }
        return _results2;
      }).apply(this);
      minima = this.concaveMinima(rows, cols, matrix);
      for (_k = 0, _len = cols.length; _k < _len; _k++) {
        col = cols[_k];
        if (col > values.length) {
          values.push(minima[col][0]);
          indices.push(minima[col][1]);
        } else if (minima[col][0] < values[col]) {
          values[col] = indices[col] = minima[col];
        }
      }
      finished = i;
      return;
    }
    diag = matrix(i - 1, i);
    if (diag < values[i]) {
      values[i] = diag;
      indices[i] = base = i - 1;
      tentative = finished = i;
      return;
    }
    if (matrix(i - 1, tentative) >= values[tentative]) {
      finished = i;
      return;
    }
    base = i - 1;
    tentative = finished = i;
  };

  OnlineConcaveMinima.prototype.concaveMinima = function(rows, cols, matrix) {
    var col, i, lastrow, mCols, minima, pair, pair1, r, row, s, _i, _len, _ref, _ref2, _ref3;
    if (!cols || cols.length === 0) return [];
    s = [];
    for (_i = 0, _len = rows.length; _i < _len; _i++) {
      r = rows[_i];
      while (s.length > 0 && (matrix(s[s.length - 1], cols[s.length - 1]) > (_ref = matrix(r, cols[s.length - 1])) && _ref > 0)) {
        s.pop();
      }
      if (s.length !== cols.length) s.push(r);
    }
    rows = s;
    mCols = [];
    for (i = 1, _ref2 = cols.length; i < _ref2; i += 2) {
      mCols.push(cols[i]);
    }
    minima = this.concaveMinima(rows, mCols, matrix);
    r = 0;
    for (i = 0, _ref3 = cols.length; i < _ref3; i += 2) {
      col = cols[i];
      row = rows[r];
      lastrow = i === cols.length - 1 ? rows[rows.length - 1] : minima[cols[i + 1]][1];
      pair = [matrix(row, col), row];
      while (row !== lastrow) {
        row = rows[++r];
        pair1 = [matrix(row, col), row];
        if (pair[0] < pair1[0]) continue;
        if (pair[0] === pair1[0] && pair[1] < pair1[1]) continue;
        pair = pair1;
      }
      minima[col] = pair;
    }
    return minima;
  };

  return OnlineConcaveMinima;

})();