Optimal Bound on the Combinatorial Complexity of Approximating Polytopes Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean ddimensional space (where d is a constant) along with an error parameter e u003e 0. The objective is to determine a polytope of low combinatorial complexity whose Hausdorff distance from K is at most e. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid1970u0027s, a result by Dudley showed that O(1e (dxe2x88x921)2) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices. While both results match known worstcase lower bounds, obtaining a similar upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a first step forward towards this objective, obtaining a suboptimal bound. In this paper, we settle this problem with an asymptotically optimal bound of O(1e (dxe2x88x921)2). Our result is based on a new relationship between ewidth caps of a convex body and its polar. Using this relationship, we are able to obtain a volumesensitive bound on the number of approximating caps that are essentially different. We achieve our result by combining this with a variant of the witnesscollector method and a novel variablewidth layered construction.

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1eps)approximations in f(k,eps)nO(1) time where k is some parameter of the input. We obtain the following results on parameterized approximability: 1) In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximumcardinality subset of pairwise nonoverlapping rectangles. This problem is NPhard and also W1hard Marx, ESAu002705. The bestknown polynomialtime approximation factor is O(loglog n) Chalermsook and Chuzhoy, SODAu002709 and it admits a QPTAS Adamaszek and Wiese, FOCSu002713; Chuzhoy and Ene, FOCSu002716. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant epsu003e0 and integer ku003e0, in time f(k,eps)ng(eps), either outputs a solution of size at least k(1eps), or declares that the optimum solution has size less than k. 2) In the (2dimensional) geometric knapsack problem (TDK) we are given an axisaligned square knapsack and a collection of axisaligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of TDK with rotations (TDKR), we are allowed to rotate items by 90 degrees. Both variants are NPhard, and the bestknown polynomialtime approximation factors are 558325eps and 43eps, resp. Galvez et al., FOCSu002717. These problems admit a QPTAS for polynomially bounded item sizes Adamaszek and Wiese, SODAu002715. We show that both variants are W1hard. Furthermore, we present a PAS for TDKR. For all considered problems, getting time f(k,eps)nO(1), rather than f(k,eps)ng(eps), would give FPT time fu0027(k)nO(1) exact algorithms using eps1(k1), contradicting W1hardness.