Anchored rectangle and square packings

DOI10.1016/J.DISOPT.2017.08.003MaRDI QIDQ1751252zbMATH OpenOpenAlexFDO

Authors Kevin Balas, Adrian Dumitrescu, Csaba D. Tóth

Publication date 24 May 2018

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/5905/

zbMATH Keywords

anchored rectangleapproximation algorithmcharging schemegreedy algorithmrectangle packing

Mathematics Subject Classification ID

Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Anchored rectangle and square packings
• Maximum area axis-aligned square packings
• Packing boundary-anchored rectangles and squares
• On the number of anchored rectangle packings for a planar point set

Cites work

• A combinatorial theorem on labeling squares with points and its application
• A constant-factor approximation for multi-covering with disks
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Algorithms – ESA 2005
• Approximation algorithms for maximum independent set of pseudo-disks
• Computing the Largest Empty Rectangle
• Elastic labels around the perimeter of a map
• scientific article; zbMATH DE number 2173815 (Why is no real title available?)
• scientific article; zbMATH DE number 3305794 (Why is no real title available?)
• scientific article; zbMATH DE number 3408456 (Why is no real title available?)
• Improved approximation algorithm for two-dimensional bin packing
• Label placement by maximum independent set in rectangles
• Labeling points with given rectangles
• LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES
• Mathematical mind-benders
• Maximum area independent sets in disk intersection graphs
• Maximum independent set of rectangles
• Multi cover of a polygon minimizing the sum of areas
• On covering problems of Rado
• On Steiner’s Problem with Rectilinear Distance
• On the largest empty axis-parallel box amidst \(n\) points
• On the number of anchored rectangle packings for a planar point set
• Point labeling with sliding labels
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• Some Covering Theorems (I)
• Some Covering Theorems (II)
• Some Covering Theorems (III)

Cited in

(8)

• Packing boundary-anchored rectangles and squares
• Anchored rectangle and square packings
• On the number of anchored rectangle packings for a planar point set
• On the number of anchored rectangle packings for a planar point set
• Maximum area axis-aligned square packings
• On the complexity of anchored rectangle packing
• On greedily packing anchored rectangles
• The reach of axis-aligned squares in the plane

This page was built for publication: Anchored rectangle and square packings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751252)