ﻻ يوجد ملخص باللغة العربية
We study several problems on geometric packing and covering with movement. Given a family $mathcal{I}$ of $n$ intervals of $kappa$ distinct lengths, and another interval $B$, can we pack the intervals in $mathcal{I}$ inside $B$ (respectively, cover $B$ by the intervals in $mathcal{I}$) by moving $tau$ intervals and keeping the other $sigma = n - tau$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $kappa$, $tau$, and $sigma$ as single parameter, but are FPT with combined parameters $kappa$ and $tau$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(nlog^2 n)$ time algorithm for covering, when all intervals in $mathcal{I}$ have the same length.
In the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon $mathcal P$ and an integer $k$, and the question is if there exist $k$ convex polygons whose union is $mathcal P$. It is known that MCC is $mathsf{NP}$-hard [Culberson & Reckhow
We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed.
We study the $c$-approximate near neighbor problem under the continuous Frechet distance: Given a set of $n$ polygonal curves with $m$ vertices, a radius $delta > 0$, and a parameter $k leq m$, we want to preprocess the curves into a data structure t
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark 90, Raghavan and Spinrad 03] to translates of any fixed convex set
A well-known conjecture of Tuza asserts that if a graph has at most $t$ pairwise edge-disjoint triangles, then it can be made triangle-free by removing at most $2t$ edges. If true, the factor 2 would be best possible. In the directed setting, also as