smawk
Version 0 revision 0 uploaded by EdwardKmett.
Package meta
- Synopsis
- Linear time row minima for totally monotone matrices
- Description
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.
- Author
- Edward Kmett
- Bug reports
- n/a
- Category
- FFI
- Copyright
- Copyright (c) 2019 Edward Kmett
- Homepage
- https://github.com/ekmett/codex/tree/master/smawk#readme
- Maintainer
- Edward Kmett <ekmett@gmail.com>
- Package URL
- n/a
- Stability
- experimental