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.
My Menu
Saved Items

A New Dynamic Programming Algorithm for Orthogonal Ruler Folding Problem in d-Dimensional Space

Ali NourollahContact Information and Mohammad Reza Razzazi1, 2 Contact Information

(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


Contact Information Ali Nourollah
Email: nourollah@aut.ac.ir

Contact Information Mohammad Reza Razzazi
Email: razzazi@aut.ac.ir
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.111 • Server: mpweb05
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)