ArticleslgStudy

mathematics

Rectangulations

Rectangulations is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Rectangulations rather than just read about it. In short: In discrete mathematics, a rectangulation (or mosaic floorplan) R {\displaystyle {\mathcal {R}}} is a decomposition of a rectangle into finitely many interior-disjoint rectangles. The size of a rectangulation describes the number of rectangles used in the decomposition.

Rectangulations — main illustration
Rectangulations — illustration

Key takeaways

  • Rectangulations belongs to mathematics; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Rectangulations to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Rectangulations from memory before moving on to harder problems.

Reference excerpt

In discrete mathematics, a rectangulation (or mosaic floorplan) R {\displaystyle {\mathcal {R}}} is a decomposition of a rectangle into finitely many interior-disjoint rectangles. The size of a rectangulation describes the number of rectangles used in the decomposition. A segment s {\displaystyle s} of a rectangulation is a maximal straight line segment, which is not contained in a side of R {\displaystyle {\mathcal {R}}} . The neighbors of a segment s {\displaystyle s} are those segments with an endpoint on s . {\displaystyle s.} If no four rectangles meet in a point the rectangulation is called generic (or mosaic). Furthermore, every generic rectangulation of size n {\displaystyle n} has exactly n − 1 {\displaystyle n-1} segments. This article will consider every rectangulation to be generic, if not stated otherwise. This topic is closely related to guillotine partitions and has applications in integrated circuit design, where floorplanning represents an early step in the design flow.

Definitions

Left-right and above-below order on rectangles A rectangle r {\displaystyle r} of the is to the left of a rectangle r ~ {\displaystyle {\tilde {r}}} if there exists a sequence of rectangles r = r 1 , r 2 , … , r k = r ~ {\displaystyle r=r_{1},r_{2},\ldots ,r_{k}={\tilde {r}}} , such that for i = 1 , … , k − 1 {\displaystyle i=1,\ldots ,k-1} the right side of r i {\displaystyle r_{i}} is contained in the same segment as the left side of r i + 1 {\displaystyle r_{i+1}} . In this case we equivalently say r ~ {\displaystyle {\tilde {r}}} is to the right of r {\displaystyle r} . A rectangle r {\displaystyle r} of the is above a rectangle r ~ {\displaystyle {\tilde {r}}} if there exists a sequence of rectangles r = r 1 , r 2 , … , r k = r ~ {\displaystyle r=r_{1},r_{2},\ldots ,r_{k}={\tilde {r}}} , such that for i = 1 , … , k − 1 {\displaystyle i=1,\ldots ,k-1} the top side of r i {\displaystyle r_{i}} is contained in the same segment as the bottom side of r i + 1 {\displaystyle r_{i+1}} . In this case we equivalently say r ~ {\displaystyle {\tilde {r}}} is below r {\displaystyle r} . Using this order we can show that every pair distinct of rectangles satisfies exactly one of these relations.

Weak and strong equivalence

For two rectangulations R 1 {\displaystyle {\mathcal {R}}_{1}} and R 2 {\displaystyle {\mathcal {R}}_{2}} we define two types of equivalence:

R 1 {\displaystyle {\mathcal {R}}_{1}} and R 2 {\displaystyle {\mathcal {R}}_{2}} are weakly equivalent, if there exists a (unique) bijection between the rectangles of R 1 {\displaystyle {\mathcal {R}}_{1}} and R 2 {\displaystyle {\mathcal {R}}_{2}} preserving the left-right and above-below orders.

… excerpt ends here. Continue reading the full article.

Illustrations

Rectangulations: A rectangulation of size 6, with all rectangles labeled in NW-SE order.
A rectangulation of size 6, with all rectangles labeled in NW-SE order.
Rectangulations: Four rectangulations of size 5. The rectangulations R 1 , R 3 {\displaystyle {\mathcal {R}}_{1},{\mathcal {R}}_{3}} and R 4 {\displaystyle {\mathcal {R}}_{4}} are weakly equivalent and the rectangulations R 1 {\displaystyle {\mathcal {R}}_{1}} and R 3 {\displaystyle {\mathcal {R}}_{3}} are strongly equivalent.
Four rectangulations of size 5. The rectangulations R 1 , R 3 {\displaystyle {\mathcal {R}}_{1},{\mathcal {R}}_{3}} and R 4 {\displaystyle {\mathcal {R}}_{4}} are weakly equivalent and the rectangulations R 1 {\displaystyle {\mathcal {R}}_{1}} and R 3 {\displaystyle {\mathcal {R}}_{3}} are strongly equivalent.
Rectangulations: Labeled rectangles of a rectangulation starting at NW-corner(left) and starting at SW-corner(right).
Labeled rectangles of a rectangulation starting at NW-corner(left) and starting at SW-corner(right).
Rectangulations: A guillotine rectangulation(left) and a non-guillotine rectangulation(right)
A guillotine rectangulation(left) and a non-guillotine rectangulation(right)
Rectangulations: A pointset P {\displaystyle P} in a rectangle(left) with two different possible rectangulations constructed on the points. In the center a guillotine rectangulation is shown and on the right a non-guillotine rectangulation is shown.
A pointset P {\displaystyle P} in a rectangle(left) with two different possible rectangulations constructed on the points. In the center a guillotine rectangulation is shown and on the right a non-guillotine rectangulation is shown.

Worked examples

Example 1 — a first encounter with Rectangulations

Start with the simplest possible case. Write down what Rectangulations claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Rectangulations before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Rectangulations ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Rectangulations

In research
Rectangulations appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Rectangulations in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Rectangulations is common in secondary-school and first-year university syllabi. It links to neighbouring topics Discrete mathematics, Integrated circuits, Rectangular subdivisions, so understanding it makes those chapters shorter.
In everyday life
Look for Rectangulations outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Rectangulations in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Rectangulations means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Rectangulations out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Rectangulations in simple terms?

In discrete mathematics, a rectangulation (or mosaic floorplan) R {\displaystyle {\mathcal {R}}} is a decomposition of a rectangle into finitely many interior-disjoint rectangles. The size of a rectangulation describes the number of rectangles used in the decomposition.

Why does Rectangulations matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Rectangulations?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Rectangulations.

Tags

  • Discrete mathematics
  • Integrated circuits
  • Rectangular subdivisions

Keep exploring