Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I agree with the previous comment made by "mu is too short". One algorithm that solves your problem could partition all existing "black" rectangles into one to three geometrical clusters based on <em>the multiplication of horizontal and vertical components</em> of the distance between each pair of "black" rectangles (this will give you the <em>area</em> of a hypothetical "red" rectangle formed between each pair), and then bind each resulting cluster with a "red" rectangle.</p> <p>Regardless of which geometric clustering algorithm you choose to solve that component of the problem (more on this below), it is important that you do not partition the "black" rectangles into clusters using the "straight", or euclidean distance between each pair as a parameter, as your problem involves reducing the <em>area</em> of bounding ("red") rectangles. As I mention in the preceding paragraph you would need to <em>multiply</em> the horizontal and vertical components of the distance between each pair of "black" rectangles in order to take account for the <em>area</em> a possible bounding "red" rectangle would cover.</p> <p>There are many geometric clustering algorithms in the literature with differing time-space complexity trade-offs, I would suggest you start with <a href="http://www.google.com/search?hl=en&amp;safe=off&amp;q=geometric+clustering+algorithms&amp;btnG=Search" rel="nofollow">this Google search</a> and get acquainted with those. Alternatively, this problem can be solved without the use of a clustering algorithm by using a <a href="http://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow">genetic</a>, or <a href="http://en.wikipedia.org/wiki/Simulated_annealing" rel="nofollow">simulated annealing</a> algorithm, in which case, the total area of various combinations and number of possible bounding "red" rectangles would be attempted and measured in order to produce an optimal solution.</p> <p>Feel free to ask for any needed clarification, and good luck with your project!</p>
    singulars
    1. This table or related slice is empty.
    1. POGiven a set of rectangles, find 3 bounding rectangles with the smallest area
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USdave
    1. USdave
    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
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    1. COThe algorithm you gave doesn't work. For example, if there are four squares diagonally ordered, then the algorithm you gave might create two bounding boxes -- one pairing the inner two, and another bounding the outer two. Also, the problem with an infinite number of bounding boxes has a *very* different complexity -- the solutions aren't related.
      singulars
      1. PO
      1. USVanwaril
    2. CO@Vanwaril The algorithm I provided works for the relaxed version of the problem I have formulated (unlimited bounding rectangles). In the example you cite ("four squares diagonally ordered"), the algorithm will *never* bind the "inner two" rectangles, and then bind the "outer two" due to the fact that in step 2., the list "binary-clusters" is sorted in ascending order by the area resulting from binding each pair of "black" rectangles, i.e. all "black" rectangles will already be bound by the time the algorithm reaches the "outer two" rectangles, *for they will be at the end of the sorted list*.
      singulars
      1. PO
      1. USdave
    3. CO@Vanwaril The fact that the relaxed version of the problem I have stated has a different complexity than the original problem has not escaped from me. The purpose of a relaxed version of a problem is to illustrate a possible direction in solving the original problem, relaxed versions of problems are often formulated in algorithm design for *didactic* purposes, and in order to formulate admissible heuristics.
      singulars
      1. PO
      1. USdave
 

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