homepage: https://github.com/ekmett/codex/tree/master/smawk#readme
changelog-type: markdown
hash: b0f272dbd22354feb9346e2ba148aeebb796976a98a75e7d50cd3f85d20047b6
test-bench-deps: {}
maintainer: Edward Kmett <ekmett@gmail.com>
synopsis: Linear time row minima for totally monotone matrices
changelog: |
  # 0
  * Written
basic-deps:
  semigroupoids: '>=5 && <6'
  base: '>=4.11 && <5'
  transformers: ^>=0.5.5
  primitive: ^>=0.7
all-versions:
- '0'
author: Edward Kmett
latest: '0'
description-type: markdown
description: |
  smawk
  =====

  [![Hackage][hackage-shield]][hackage]

  This package implements the SMAWK algorithm by
  [Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber and Maria Klawe][smawk]
  for finding the minimum value in each row of an implicitly defined totally monotone matrix.

  This has many applications in computational geometry, such as finding the farthest point
  from each point in a convex polygon, finding optimal enclosing polygon. It can also be
  used to implement paragraph line breaking in a manner analogous to Knuth and Platt, but in
  linear time. It also has uses in RNA secondary structure prediction, various sequence
  alignment problems, construction of prefix codes, image thresholding, etc.

  Contact Information
  -------------------

  Contributions and bug reports are welcome!

  Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.

  -Edward Kmett

  [smawk]: https://link.springer.com/article/10.1007%2FBF01840359
  [hackage]: https://hackage.haskell.org/package/smawk
  [hackage-shield]: https://img.shields.io/hackage/v/smawk.svg
license-name: (BSD-2-Clause OR Apache-2.0)

Update from Hackage at 2021-03-24T02:33:36Z
Update from Hackage at 2021-03-24T02:33:36Z
