English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Recently, Adamaszek and Wiese [1, 2] presented a quasi-polynomial time approximation scheme (QPTAS) for the problem of computing a maximum weight independent set for certain families of planar objects. This major advance on the problem was based on their proof that a certain type of separator exists for any independent set. Subsequently, Har-Peled [22] simplified and generalized their result. Mustafa et al. [36] also described a simplification, and somewhat surprisingly, showed that QPTAS's can be obtained for certain, albeit special, type of covering problems.  Building on these developments, we revisit two NP-hard geometric partitioning problems -- convex decomposition and surface approximation. Partitioning problems combine the features of packing and covering. In particular, since the optimal solution does form a packing, the separator theorems are potentially applicable. Nevertheless, the two partitioning problems we study bring up additional difficulties that are worth examining in the context of the wider applicability of the separator methodology. We show how these issues can be handled in presenting quasi-polynomial time algorithms for these two problems with improved approximation guarantees.

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation