Computing Instance-Optimal Kernels in Two Dimensions

Pankaj K. Agarwal, Sariel Har-Peled

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication39th International Symposium on Computational Geometry, SoCG 2023
EditorsErin W. Chambers, Joachim Gudmundsson
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772730
DOIs
StatePublished - Jun 1 2023
Externally publishedYes
Event39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, United States
Duration: Jun 12 2023Jun 15 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume258
ISSN (Print)1868-8969

Conference

Conference39th International Symposium on Computational Geometry, SoCG 2023
Country/TerritoryUnited States
CityDallas
Period6/12/236/15/23

Keywords

  • Coreset
  • approximation
  • kernel

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Computing Instance-Optimal Kernels in Two Dimensions'. Together they form a unique fingerprint.

Cite this