Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Not a complete solution, but a simplification of the problem: Assume that all points P are in general position and are sorted on x-coordinate.</p> <p>The solution is then formed by finding F vertical fences (of the form <code>x &gt;= fx</code>) that partition P into disjoint sets. </p> <p>Each set can then be covered by an axis-aligned rectangle, where the first and last points in the set determine the width of the rectangle, and the point in the set with the highest y-coordinate determines the height, hereby determining the surface size of the rectangle.</p> <p>Obviously, the trick is now to choose the fences in such a way that the number of fences (and hereby the number of rectangles) is minimized, while keeping the total surface size of all rectangles under the allowed maximum.</p> <p><strong>Edit</strong><br> <strike>Possibly the problem of placing the F fences <em>can</em> be solved using dynamic programming. </strike> This is what I've come up with so far: </p> <p>If so, there are at most |P|-1 fence locations; these will probably become the columns in the dynamic programming table. Each row in the dynamic programming table should represent using an additional fence (remember, we're trying to find the result with the least number of fences). Each cell (X, Y), then, would represent the optimal solution (in terms of total rectangle size) of distributing exactly Y fences over the first X available positions. However, I'm having a bit of a problem seeing how (or if) the neighbouring cells of the table can help in determining the value of a particular cell.</p> <p><strong>Edit 2</strong>: Forget that, I don't think a dynamic programming approach is possible. This is because I believe it's not possible to construct an optimal solution incrementally (the optimal solution configuration may change completely by adding another point or fence). This would also rule out a greedy approach.</p> <p>The only think I can think of, although a little less spectactular from an algorithmic point of view, is a randomized approach such as <a href="http://en.wikipedia.org/wiki/Simulated_annealing" rel="nofollow">Simulated annealing</a> for distributing the fences. It doesn't guarantee <em>the</em> optimal solution, but you should be able to get pretty close to it.</p> <p><strong>Edit 3</strong>: In response to the reaction under this post, how about we don't necessarily require the <em>best</em> solution, but go for a 'pretty good' solution instead, and apply what you're learning right now.</p> <p>In any case, you'll probably need to sort all points from left to right.</p> <p>A greedy solution could be to define the first rectangle so that it includes the leftmost point. Next, expand the rectangle so that it includes the point to the right of it. Keep adding the next point until the rectangle would exceed its maximum size. In that case, start with a new rectangle and start adding points again, etc.</p> <p>A divide and conquer way of obtaining a solution could be to start with the rectangle that covers all the points. Obviously, this rectangle exceeds the maximum size M, so you split it vertically into 2 smaller rectangles Ml and Mr, according to some heuristic (exactly down the middle, or at the point where two subsequent points are furthest apart, for example). Recursively process Ml and Mr in the same way, either splitting the rectangles again or reporting the found rectangle as part of the result if it is &lt;= M. </p> <p>Note that for both approaches, the results could be arbitrarily bad for some contrived configurations, but in general the solutions should be 'ok'.</p>
    singulars
    1. This table or related slice is empty.
    1. POContaining algorithm for cartesian surface items
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAstrotrain
    1. USAstrotrain
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou lost me with all these programming methods. If it helps, dynammic programming and the Greedy method were two of the chapters of the course the assignment is for. I am currently trying to use about Divide et Impera and recursivity but no result yet...
      singulars
      1. PO
      1. USb1nnar
    2. CO@binar: No problem :) I've added some new suggestions.
      singulars
      1. PO
      1. USAstrotrain
    3. COI have already considered these two approaches on the paper. I guess I'll stick with one of them or start reading all the courses of the professor... Thanks a lot, Astrotrain.
      singulars
      1. PO
      1. USb1nnar
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload