smawk: Linear time row minima for totally monotone matrices
This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.
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]
Properties
| Versions | 0, 0 |
|---|---|
| Change log | CHANGELOG.md |
| Dependencies | base (>=4.11 && <5), primitive (>=0.7 && <0.8), semigroupoids (>=5 && <6), 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:24:47Z |
Modules
[Index] [Quick Jump]
- Data
Downloads
- smawk-0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
Package maintainers
For package maintainers and hackage trustees
Readme for smawk-0
[back to package description]smawk
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