An approximation algorithm for dissecting a rectangle into rectangles with specified areas

Hiroshi Nagamochi, Yuusuke Abe

Type: Article

Publication Date: 2006-10-11

Citations: 33

DOI: https://doi.org/10.1016/j.dam.2006.08.005

View Publication

Locations

Discrete Applied Mathematics - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	A Divide and Conquer Approximation Algorithm for Partitioning Rectangles	2023	Reyhaneh Mohammadi Mehdi Behroozi
+	A Divide and Conquer Approximation Algorithm for Partitioning Rectangles	2023	Reyhaneh Mohammadi Mehdi Behroozi
+	Finding Largest Rectangles in Convex Polygons	2014	Sergio Cabello Otfried Cheong Christian Knauer Lena Schlipf
+	Finding Largest Rectangles in Convex Polygons	2014	Sergio Cabello Otfried Cheong Christian Knauer Lena Schlipf
+	Rectangle Transformation Problem	2017	Shaojiang Wang Kun He Yicheng Pan Mingji Xia
+	Maximizing the area of intersection of rectangles	2017	D. B. A. Epstein Mike Paterson
+	Dissection of Rectangles into Largest Possible Squares	2021	Heinz Klaus Strick
+	The Maximum Exposure Problem	2021	Neeraj Kumar Stavros Sintos Subhash Suri
+	The Maximum Exposure Problem.	2021	Neeraj Kumar Stavros Sintos Subhash Suri
+	A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment.	2015	Sayan Bandyapadhyay Santanu Bhowmick Kasturi Varadarajan
+	The decomposition of a rectangle into rectangles of minimal perimeter	1986	Bill Roscoe
+	A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment	2015	Sayan Bandyapadhyay Santanu Bhowmick Kasturi Varadarajan
+	Maximum-width Axis-Parallel Empty Rectangular Annulus	2017	Arpita Baral Abhilash Gondane Sanjib Sadhu Priya Ranjan Sinha Mahapatra
+	On the Minimum-Area Rectangular and Square Annulus Problem	2019	Sang Won Bae
+	On the Minimum-Area Rectangular and Square Annulus Problem	2019	Sang Won Bae
+ PDF Chat	Optimal Rectangle Packing: An Absolute Placement Approach	2013	Eric Huang Richard E. Korf
+	Maximum-width Axis-Parallel Empty Rectangular Annulus.	2017	Arpita Baral Abhilash Gondane Sanjib Sadhu Priya Ranjan Sinha Mahapatra
+	Partitioning a rectangle into many sub-rectangles so that a line can meet only a few	1993	Daniel J. Kleitman
+	A note on finding a maximum empty rectangle	1986	Mikhail J. Atallah Greg N. Frederickson
+	A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles	2021	Waldo Gálvez Arindam Khan Mathieu Mari Tobias Mömke M. Thirupathi Reddy Andreas Wiese

Works That Cite This (5)

Action	Title	Year	Authors
+ PDF Chat	On three soft rectangle packing problems with guillotine constraints	2019	Quoc Trung Bui Thibaut Vidal Minh Hoàng Hà
+ PDF Chat	Quantitative Comparison of Time‐Dependent Treemaps	2020	Eduardo Faccin Vernier Max Sondag João L. D. Comba Bettina Speckmann Alexandru Telea Kevin Verbeek
+	Layer Based Partition for Matrix Multiplication on Heterogeneous Processor Platforms	2018	Yang Liu Shi Li Junwei Zhang Thomas G. Robertazzi
+	Quantitative Comparison of Time-Dependent Treemaps	2019	Eduardo Faccin Vernier Max Sondag João L. D. Comba Bettina Speckmann Alexandru Telea Kevin Verbeek
+ PDF Chat	A Divide and Conquer Approximation Algorithm for Partitioning Rectangles	2023	Reyhaneh Mohammadi Mehdi Behroozi

Works Cited by This (5)

Action	Title	Year	Authors
+	Dissections: Plane and Fancy	1997	Greg N. Frederickson
+	Tiling a Rectangle with the Fewest Squares	1996	Richard Kenyon
+	The mathematical Gardner	1982	David A. Klarner
+	The decomposition of a square into rectangles of minimal perimeter	1987	T. Yung Kong David M. Mount Michael Werman
+	Tiling a polygon with rectangles	1992	Claire Kenyon Richard Kenyon