FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Research
Algorithm to fit rectangles with different areas inside a matrix with lowest complexity
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
Author Message
Dani Camps
science forum beginner


Joined: 07 Jul 2006
Posts: 2

PostPosted: Tue Jul 11, 2006 9:14 am    Post subject: Algorithm to fit rectangles with different areas inside a matrix with lowest complexity Reply with quote

Hi everybody,

I have the following problem:

I have a matrix with M rows and N columns. Then I have a set of objects
that I have to fit in, and the area they have depends on where I will
place them in the matrix. Let's give an example:

Object 1:
-You can place it between rows 2 and 4 of the matrix, and if you do so
the are of the object is 10.
-You can place it between rows 3 and 7 of the matrix,and if you do so
the area of the object is 20
....

We have up to Li rules like this for every one of the objects. And the
rules are really like described in the example, they define a set of
rows and the area that the object will have if it is placed within
these rows. The way the actual filling is done, i. e. the shape that
the object will have between the rows in the matrix is in principle
irrelevant, but it is preferable if it is rectangular, this means that
given a set of rows and an area I either start filling by columns or by
rows.

You can also imagine that the rules are ordered in terms of area of the
object, if we allocate the object according to the first rule then the
area it takes is the smallest one, if we allocate the object according
to the last rule then the area is the biggest one.

So now I am given x objects each one with it x_l number of rules
ordered by area, and I have this matrix MxN. The problem is to find the
allocation of the objects that minimizes the occupied area in the
matrix.

Intuitively I would start trying to place all the objects according to
their rule number one, the one where they have the smallest area, if
all the objects fit without overlapping I am finished and this is the
optimum allocation, but if I can not allocate two objects in their best
rule because the matrix is not big enough then I have to decide to
place one of them there and go
for the second rule of the other object, that in turn can collide with
another object's allocation.

The trivial solution is the exhaustive search but this is too time
consuming.

Can you point me to some algorithms, that try to solve problems similar
to this in an optimum way ?

Thanks

Dani
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
The time now is Wed Jun 28, 2017 7:06 pm | All times are GMT
Forum index » Science and Technology » Math » Research
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Diagonalizable matrix aline Math 0 Wed Nov 29, 2006 3:08 am
No new posts how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am
No new posts sign of the determinant of an augmented matrix? Mark Math 4 Thu Jul 20, 2006 1:30 am
No new posts spectrum of a symmetric tridiagonal random matrix pf.buonsante@gmail.com Math 0 Wed Jul 19, 2006 9:45 am
No new posts Complexity of Sparse Cholesky Factorization crazyFritz Research 0 Mon Jul 17, 2006 2:24 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0177s ][ Queries: 16 (0.0041s) ][ GZIP on - Debug on ]