Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>Choose colours, not boxes!</h2> <p>At any point in time, one or more boxes will be <em>paintable</em>, i.e. they are able to be painted next without introducing problems (though possibly introducing a cost due to having a different colour from the most recently painted box).</p> <p>The question at every point is: What <strong>colour</strong> should we pick to draw next? It's not necessary to think about picking individual paintable boxes to draw, because as soon as you pick a particular box to draw next, you might as well draw all available boxes of the same colour that can be drawn at that time. That's because painting a box never <em>adds</em> constraints to the problem, it only removes them; and choosing not to paint a paintable box when you could do so without changing the current colour cannot make the solution less expensive than it would otherwise be, since you will later have to paint this box and that may require a colour change. This also means it doesn't matter in which order we paint paintable boxes of the same colour, since we will paint all of them at once in a single "block" of box painting operations.</p> <h2>The dependency graph</h2> <p>Start by building a "lies underneath" dependency graph, where each coloured rectangle is represented by a vertex and there is an arc (arrow) from v to u if rectangle v overlaps rectangle u and lies underneath it. My first thought was to use this to build a "must be drawn before" dependency graph by finding the transitive closure, but actually we don't need to do this, since all the algorithms below care about is whether a vertex is paintable or not. Paintable vertices are the vertices that have no predecessors (in-arcs), and taking the transitive closure does not alter whether a vertex has 0 in-arcs or not.</p> <p>In addition, whenever a box of a given colour has only boxes of the same colour as its ancestors, it will be painted in the same "block" -- since all those ancestors can be painted before it without changing colours.</p> <h2>A speedup</h2> <p>To cut down on computation, notice that whenever all paintable boxes of some particular colour have no different-coloured descendants, painting this colour won't open up any new opportunities for other boxes to become paintable, so we don't need to consider this colour when considering which colour to paint next -- we can always leave it till later with no risk of increasing the cost. In fact it's <em>better</em> to leave painting this colour till later, since by that time other boxes of this colour may have become paintable. Call a colour <em>helpful</em> if there is at least one paintable box of that colour that has a different-coloured descendant. When we get to the point when there are no helpful colours remaining (i.e. when all remaining boxes overlap only boxes of the same colour, or no boxes at all) then we are done: just paint the boxes of each remaining colour, picking colours in any order.</p> <h2>Algorithms</h2> <p>These observations suggest two possible algorithms:</p> <ol> <li><strong>A fast but possibly suboptimal greedy algorithm:</strong> Choose to paint next the colour that produces the most new paintable vertices. (This will automatically consider only helpful colours.)</li> <li><p><strong>A slower, exact DP or recursive algorithm:</strong> For each possible helpful colour c, consider the dependency graph produced by painting all paintable c-coloured boxes next:</p> <p>Let f(g) be the minimum number of colour-changes required to paint all boxes in the dependency graph g. Then</p> <p>f(g) = 1 + min(f(p(c, g)))</p> <p>for all helpful colours c, where p(c, g) is the dependency graph produced by painting all paintable boxes of colour c. If G is the dependency graph for the original problem, then f(G) will be the minimum number of changes. The colour choices themselves can be reconstructed by tracing backwards through the DP cost matrix.</p> <p>f(g) can be <a href="http://en.wikipedia.org/wiki/Memoization" rel="noreferrer">memoised</a> to create a dynamic programming algorithm that saves time whenever 2 different permutations of colour choices produce the same graph, which will happen often. But it might be that even after DP, this algorithm could take an amount of time (and therefore space) that is exponential in the number of boxes... I will have a think about whether a nicer bound can be found.</p></li> </ol>
    singulars
    1. This table or related slice is empty.
    1. POOptimising the drawing of overlapping rectangles
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USj_random_hacker
    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. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COGood idea with the paintable boxes and the dependency graph. However, my gut tells me that building the graph will be expensive. The greedy algorithm can simply be proven to be suboptimal. The recursive algorithm could be expensive as well. Altogether this solution is possibly not a good tradeoff between js and gpu work. Code shall prove.
      singulars
      1. PO
      1. USilmiacs
    2. CO@ilmiacs: It seems to me that building that graph will be necessary in almost any approach that offers some algorithmic optimizations. But you need to do that work in any case, regardless of whether you store it in a particular data structure, so creating the graph should not add much overhead to any approach that has to understands which boxes overlap each other. But I agree that the recursive algorithm here is almost certain too expensive for reasonable sized data sets.
      singulars
      1. PO
      1. USScott Sauyet
    3. COMy gut goes with @ilmiacs but its possible perhaps that an optimal ordering computed once when you make a tree can cause the rectangles that are computed to be visible by the tree each time the screen rect moves to be in *near*-optimal general order without any further work, or with a cheapish sort? ***Code shall prove.***
      singulars
      1. PO
      1. USWill
 

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