Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
A New Dynamic Programming Algorithm for Orthogonal Ruler Folding Problem in d-Dimensional Space
| |
|
A New Dynamic Programming Algorithm for Orthogonal Ruler Folding Problem in d-Dimensional Space
Ali Nourollah1 and Mohammad Reza Razzazi1, 2 
| (1) |
Software Systems R&D Lab., Department of Computer Engineering & IT, Amirkabir University of Technology, #424 Hafez Avenue,
P. O. Box 15875-4413, Tehran, Iran |
| (2) |
Institute for Studies in Theoretical Physics and Mathematics (I.P.M.), |
Abstract
A chain or n-link is a sequence of n links whose lengths are fixed joined together from their endpoints, free to turn about their endpoints, which act as joints.
“Ruler Folding Problem”, which is NP-Complete is to find the minimum length of the folded chain in one dimensional space. The best result for ruler
folding problem is reported by Hopcroft et al. in one dimensional space which requires O(nL
2) time complexity, where L is length of the longest link in the chain and links have integer value lengths. We propose a dynamic programming approach
to fold a given chain whose links have integer lengths in a minimum length in O(nL) time and space. We show that by generalizing the algorithm it can be used in d-dimensional space for orthogonal ruler folding problem such that it requires O(2
d
ndL
d
) time using O(2
d
ndL
d
) space.
Keywords Ruler Folding Problem - Carpenter’s Ruler - Dynamic Programming
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|