Rectangulations

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In discrete mathematics, a rectangulation (or mosaic floorplan) \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 of a rectangulation is a maximal straight line segment, which is not contained in a side of \mathcal{R} . The neighbors of a segment s are those segments with an endpoint on s. If no four rectangles meet in a point the rectangulation is called generic (or mosaic). Furthermore, every generic rectangulation of size n has exactly 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.

In discrete mathematics, a rectangulation (or mosaic floorplan) \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 of a rectangulation is a maximal straight line segment, which is not contained in a side of \mathcal{R} . The neighbors of a segment s are those segments with an endpoint on s. If no four rectangles meet in a point the rectangulation is called generic (or mosaic). Furthermore, every generic rectangulation of size n has exactly 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. A rectangle r of the is to the left of a rectangle \tilde{r} if there exists a sequence of rectangles r=r_1, r_2, \ldots , r_k=\tilde{r} , such that for i=1,\ldots ,k-1 the right side of r_i is contained in the same segment as the left side of r_{i+1} . In this case we equivalently say \tilde{r} is to the right of r . A rectangle r of the is above a rectangle \tilde{r} if there exists a sequence of rectangles r=r_1, r_2, \ldots , r_k=\tilde{r} , such that for i=1,\ldots ,k-1 the top side of r_i is contained in the same segment as the bottom side of r_{i+1} . In this case we equivalently say \tilde{r} is below r . Using this order we can show that every pair distinct of rectangles satisfies exactly one of these relations. There are several known bijections between equivalence classes of rectangulations and permutation classes. In the following table p_1 and p_2 refer to the mesh patterns given by p_1=(25314,\{(0,3), (0,4), (1,3), (4,2), (5,1), (5,2)\}) and p_2=(41352,\{(0,1), (0,2), (1,2), (4,3), (5,3), (5,4)\}) . These bijections allow us to count the number of weak and strong rectangulations. For example, the number of weak rectangulations of size n is therefore given by the n -th Baxter number (sequence A001181 in the OEIS), given by the formula: B_n=\sum_{k=1}^n \frac{\binom{n+1}{k-1}\binom{n+1}{k}\binom{n+1}{k+1}}{\binom{n+1}{0}\binom{n+1}{1}\binom{n+1}{2}} for which it is known that B_n \sim \tfrac{2^{3n+5}}{n^4\pi\sqrt{3}} . Similarly the number of weak guillotine rectangulations of size n is given by the n -th Schröder number (sequence A006318 in the OEIS).

Binary search trees and rectangulations

In computer science, an approach to the dynamic optimality problem on online algorithms for binary search trees (BST) involves reformulating the problem geometrically, in terms of augmenting a set of points in the plane with as few additional points as possible to avoid rectangles with only two points on their boundary. In addition to the geometric model introduced by Demaine et al. (2009), the BST dynamic optimality problem admits an equivalent formulation in terms of rectangulations. This equivalence was established by Kozma and Saranurak (20161). When a rectangulation is constrained by a set P of points (no two sharing the same horizontal or vertical line), every point of P must lie in the interior of exactly one segment. Given an access sequence X = (x_1, \dots, x_n) with distinct keys, map it to the point set \{(x_i, i) : 1 \le i \le n\} . The initial rectangulation state consists of vertical segments through every point of X , plus the boundary margins. A valid end state consists of only horizontal segments that together cover every point of \{1, \dots, n\} on the horizontal lines y = 1, \dots, n . The Rectangulation problem asks for the minimum number of flips that transform the initial (all-vertical) state into any valid end (all-horizontal) state. A flip adds a new horizontal or vertical segment between two existing points and, if necessary, splits intersecting segments, while preserving the property that every interior point has degree at least 2 and that no two segments cross improperly (the “elbow-free” condition). In this setup, the following polynomial-time equivalence (up to constant factor) can be proven: Together with the fact that any algorithm for the Satisfied Superset problem (minimum superset of the input points that admits a Manhattan path between every pair) can be converted into a BST algorithm whose cost is \Theta of the superset size, and vice versa, this leads to the correspondence between BSTs and rectangulations. Consequently, the minimum cost of serving X in the BST model is \Theta of the minimum number of flips needed to go from the all-vertical to the all-horizontal rectangulation constrained by the points of X . This “flip view” reinterprets classic BST algorithms (Splay, Greedy, etc.) as particular flip strategies and yields new algorithmic perspectives: the sequence of flips builds the BST solution in an order dictated by the internal structure of the query sequence, and progress toward the all-horizontal target is measurable. The model further connects (up to an additive O(n) term) to the Tree Relaxation problem: starting from the treap on X (with y-coordinates as priorities), repeatedly perform valid edge flips (reparenting a child to a neighboring sibling under certain conditions) until reaching the unique root-to-leaf path ordered by increasing y-coordinate. This relaxation view highlights progress via strictly decreasing total edge height or increasing total edge width. Some additional remarks: The flip diameter of rectangulations (maximum distance between any two rectangulations on the same point set under flip/rotate operations) is \Theta of the BST optimum for certain inputs. The Small Manhattan Network optimum is a lower bound on the BST optimum, and the two quantities coincide asymptotically on many inputs (including random permutations and pattern-avoiding point sets). Upper bounds (dynamic finger, working set, etc.) and heuristics for BSTs arise naturally from optimization measures on intermediate rectangulations or monotone trees (total edge length, total distance from root, etc.). Sets of interior-disjoint axis-aligned rectangles in space are called Plattenbauten. They are a generalization of axis-aligned segment contacts in two dimensions. The touching graph of a Plattenbau has one vertex for each rectangle, two vertices are connected by an edge, if the corresponding rectangles touch. It can be shown that every 3-colorable planar graph ist the touching graph of a generic Plattenbau. A Plattenbau G=(V,E) is generic, if there are no coplanar rectangles. It has the following properties: chromatic number \chi(G)\leq3 neighborhood N(v) is planar \forall v\in V the smallest dimension d such that G is an intersection graph of d -boxes is at most 3 .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1363078514 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia date of establishment (×1) · confidence 0.95 https://en.wikipedia.org/w/index.php?oldid=1363078514