TY - GEN

T1 - Computing Instance-Optimal Kernels in Two Dimensions

AU - Agarwal, Pankaj K.

AU - Har-Peled, Sariel

N1 - Publisher Copyright:
© Pankaj K. Agarwal and Sariel Har-Peled; licensed under Creative Commons License CC-BY 4.0.

PY - 2023/6/1

Y1 - 2023/6/1

N2 - Let P be a set of n points in R2. For a parameter (Equation presented), a subset C Ď P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (Equation presented)-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 (Equation presented) (resp. (Equation presented)) denote the minimum-size of an ε-kernel (resp. weak ε-kernel) of P. We present an (Equation presented)-time algorithm for computing an ε-kernel of P of size (Equation presented), and an (Equation presented)-time algorithm for computing a weak ε-kernel of P of size (Equation presented). 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 ch(P), 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.

AB - Let P be a set of n points in R2. For a parameter (Equation presented), a subset C Ď P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (Equation presented)-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 (Equation presented) (resp. (Equation presented)) denote the minimum-size of an ε-kernel (resp. weak ε-kernel) of P. We present an (Equation presented)-time algorithm for computing an ε-kernel of P of size (Equation presented), and an (Equation presented)-time algorithm for computing a weak ε-kernel of P of size (Equation presented). 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 ch(P), 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.

KW - Coreset

KW - approximation

KW - kernel

UR - http://www.scopus.com/inward/record.url?scp=85163545644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163545644&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2023.4

DO - 10.4230/LIPIcs.SoCG.2023.4

M3 - Conference contribution

AN - SCOPUS:85163545644

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 39th International Symposium on Computational Geometry, SoCG 2023

A2 - Chambers, Erin W.

A2 - Gudmundsson, Joachim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 39th International Symposium on Computational Geometry, SoCG 2023

Y2 - 12 June 2023 through 15 June 2023

ER -