Search   Memberlist   Usergroups
 Page 1 of 1 [1 Post]
Author Message
Dani Camps
science forum beginner

Joined: 07 Jul 2006
Posts: 2

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

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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [1 Post]
 The time now is Tue Mar 26, 2019 4:18 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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

Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters