Skip to main content

Computing Instance-Optimal Kernels in Two Dimensions

Publication ,  Conference
Agarwal, PK; Har-Peled, S
Published in: Leibniz International Proceedings in Informatics, LIPIcs
June 1, 2023

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.

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959772730

Publication Date

June 1, 2023

Volume

258
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Agarwal, P. K., & Har-Peled, S. (2023). Computing Instance-Optimal Kernels in Two Dimensions. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 258). https://doi.org/10.4230/LIPIcs.SoCG.2023.4
Agarwal, P. K., and S. Har-Peled. “Computing Instance-Optimal Kernels in Two Dimensions.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258, 2023. https://doi.org/10.4230/LIPIcs.SoCG.2023.4.
Agarwal PK, Har-Peled S. Computing Instance-Optimal Kernels in Two Dimensions. In: Leibniz International Proceedings in Informatics, LIPIcs. 2023.
Agarwal, P. K., and S. Har-Peled. “Computing Instance-Optimal Kernels in Two Dimensions.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 258, 2023. Scopus, doi:10.4230/LIPIcs.SoCG.2023.4.
Agarwal PK, Har-Peled S. Computing Instance-Optimal Kernels in Two Dimensions. Leibniz International Proceedings in Informatics, LIPIcs. 2023.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959772730

Publication Date

June 1, 2023

Volume

258