Publications [#376943] of Pankaj K. Agarwal

Papers Published

1. Agarwal, PK; Har-Peled, S, Computing Instance-Optimal Kernels in Two Dimensions, Discrete and Computational Geometry, vol. 73 no. 3 (April, 2025), pp. 674-701 [doi]
   (last updated on 2026/01/14)

   Abstract:
   Let P be a set of n points in R². For a parameter ε∈(0,1), a subset C⊆P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (1-ε)-factor in every direction. The set C is a weakε-kernel of P if its directional width approximates that of P in every direction. Let kε(P) (resp. kε^w(P)) denote the minimum-size of an ε-kernel (resp. weak ε-kernel) of P. We present an O(nkε(P)logn)-time algorithm for computing an ε-kernel of P of size kε(P), and an O(n²logn)-time algorithm for computing a weak ε-kernel of P of size kε^w(P). We also present a fast algorithm for the Hausdorff variant of this problem. In addition, we introduce the notion of ε-core, a convex polygon lying inside, prove that it is a good approximation of the optimal ε-kernel, present an efficient algorithm for computing it, and use it to compute an ε-kernel of small size.