Ruler Folding
Created Donnerstag 25 Juli 2024
A polygonal chain is a linkage whose graph is just a path. If one views it as a "carpenters ruler", it is natural to seek to fold it up int as compact a package as possible. This is known as the "ruler folding problem":
Given a polygonal cain with specific given (integer) lengths for its n links, and an integer L , can it be folded flat (each joint angle either 0 or 180°) so that its total length is ≤ L?
In 1985 it was proven that this question is NP-complete.
Backlinks: Foldability Questions