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 orderin
g 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 $mathbb{NP}$-hard, but only heuristics were known for it. We show that a certain decision version of LADR is $mathbb{APX}$-hard, and give a constant factor approximation for LADR.
We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $kappa :X rightarrow mathcal{N}$, and a constant $alpha geq 1$. Centered at each se
rver is a single disk whose radius we are free to set. The requirement is that each client $x in X$ be covered by at least $kappa(x)$ of the server disks. The objective function we wish to minimize is the sum of the $alpha$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.
We revisit two NP-hard geometric partitioning problems - convex decomposition and surface approximation. Building on recent developments in geometric separators, we present quasi-polynomial time algorithms for these problems with improved approximation guarantees.
