2015/02/12 by Sayan Bandyapadhyay, Bandyapadhyay, Sayan, Santanu Bhowmick +3
Computer Science · Engineering · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #I.3.5 #Optimization and Packing Problems #VLSI and FPGA Design Techniques #cs.CC #cs.CG #cs.DM #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1502.03847
Edited Section 5, re-arranged content
openalex publication_date 2015/02/12 · arxiv created 2015/02/23 · arxiv updated 2015/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding box and preserves the orthogonal order i.e. maintains the sorted ordering of the rectangle centers along both x-axis and y-axis with respect to the initial placement. This problem is known as Layout Adjustment for Disjoint Rectangles(LADR). It was known that LADR is \mathbbNP-hard, but only heuristics were known for it. We show that a certain decision version of LADR is \mathbbAPX-hard, and give a constant factor approximation for LADR.