smawk: Linear time row minima for totally monotone matrices

[ ffi, library ] [ Propose Tags ]

This implements the SMAWK algorithm by Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber and Maria Klawe 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.


[Skip to Readme]
Versions [faq] 0
Change log CHANGELOG.md
Dependencies base (>=4.11 && <5), primitive (==0.7.*), semigroupoids (==5.*), transformers (>=0.5.5 && <0.6) [details]
License (BSD-2-Clause OR Apache-2.0)
Copyright Copyright (c) 2019 Edward Kmett
Author Edward Kmett
Maintainer Edward Kmett <ekmett@gmail.com>
Category FFI
Home page https://github.com/ekmett/codex/tree/master/smawk#readme
Source repo head: git clone https://github.com/ekmett/codex(smawk)
Uploaded by EdwardKmett at 2021-03-24T02:25:35Z
Distributions NixOS:0
Downloads 33 total (7 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs uploaded by user
Build status unknown [no reports yet]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for smawk-0

[back to package description]

smawk

Hackage

This package implements the SMAWK algorithm by Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber and Maria Klawe 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