A Tailor's Problem

Thread View: sci.math.num-analysis

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by chr09tk Tue, 01 Sep 1992 17:07

#398

Author: chr09tk
Date: Tue, 01 Sep 1992 17:07

11 lines
749 bytes

Hello!

I would be grateful for any refferences concerning the following problem:

We are given a roll of cloth of a given width and unlimited length. We are also
given a finite set of polygons (pieces of clothing). We want to cut out the
polygons using a minimal length of the cloth. Devise an algorithm that will get
us as close as possible to the minimum (within reasonable time). 

Thanks in advance,
Haggai Katriel

Re: A Tailor's Problem

#400

Author: Eli Chiprout
Date: Tue, 01 Sep 1992 18:21

13 lines
969 bytes

In <1992Sep1.190730.1@vmsa.technion.ac.il> chr09tk@vmsa.technion.ac.il writes:
>We are given a roll of cloth of a given width and unlimited length. We are also
>given a finite set of polygons (pieces of clothing). We want to cut out the
>polygons using a minimal length of the cloth. Devise an algorithm that will get
>us as close as possible to the minimum (within reasonable time). 

Sounds like the travelling salesman again -- NP complete at best.

--
Eli Chiprout
Dept. of Electronics, Carleton University
Ottawa, Ontario, Canada
emc@doe.carleton.ca

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads