554 An Upper Bound on the Number of Rectangulations of a Point Set ⋆ (2008)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
Abstract. We consider the number of different ways to divide a rectangle containing n noncorectilinear points into smaller rectangles by n non-intersecting axis-parallel segments, such that every...
A Bijection Between Permutations and Floorplans, and its Applications (2008)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
A floorplan represents the relative relations between modules on an integrated circuit. Floorplans are commonly classified as slicing, mosaic, or general. Separable and Baxter permutations are...
Acyclic Orientation of Drawings ⋆ (2008)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Günter Rote
Abstract. Given a set of curves in the plane or a topological graph, we ask for an orientation of the curves or edges which induces an acyclic orientation on the corresponding planar map. Depending...
The Number of Guillotine Partitions in d Dimensions ∗ (2008)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter, Dan Romik
Guillotine partitions play an important role in many research areas and application domains, e.g., computational geometry, computer graphics, integrated circuit layout, and solid modeling, to mention...
The maximum number of edges in quasi-planar graphs, manuscript (2008)
A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [2] proved that these graphs have a linear number of edges. We give a simple proof for this...
Abstract Improved Upper Bounds on the Reflexivity of Point Sets (2008)
Eyal Ackerman, Oswin Aichholzer, Balázs Keszegh
Given a set S of n points in the plane, the reflexivity of S, ρ(S), is the minimum number of reflex vertices in a simple polygonalization of S. Arkin et al. [4] proved that ρ(S) ≤ ⌈n/2 ⌉ for...
Improved Upper Bounds on the Reflexivity of Point Sets (2008)
Eyal Ackerman, Oswin Aichholzer, Balázs Keszegh
Given a set S of n points in the plane, the reflexivity of S, ρ(S), is the minimum number of reflex vertices in a simple polygonalization of S. Arkin et al. [4] proved that ρ(S) ≤ ⌈n/2 ⌉ for...
There are not too many Magic Configurations (2007)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, Günter Rote
A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all...
There are not too many Magic Configurations (2007)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, Günter Rote
A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all...
Abstract Acyclic Orientation of Drawings ∗ (2006)
Eyal Ackerman, Kevin Buchin, Christian Knauer, Günter Rote
Given a set of curves in the plane or a topological graph, we ask for an orientation of the curves or edges which induces an acyclic orientation on the corresponding planar map. Depending on the...
On the number of rectangular partitions (2004)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
How many ways can a rectangle be partitioned into smaller ones? We study two variants of this problem: when the partitions are constrained to lie on n given points (no two of which are...
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
We investigate the number of different ways in which a rectangle containing a set of n noncorectilinear points can be partitioned into smaller rectangles by n (non-intersecting) segments, such that...