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 Tools annual

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider the Minimum Convex Partition problem: Given a set P of n pointsin the plane, draw a plane graph G on P, with positive minimum degree, suchthat G partitions the convex hull of P into a minimum number of convex faces.We show that Minimum Convex Partition is NP-hard, and we give severalapproximation algorithms, from an O(log OPT)-approximation running inO(n^8)-time, where OPT denotes the minimum number of convex faces needed, to anO(sqrt(n) log n)-approximation algorithm running in O(n^2)-time. We say that apoint set is k-directed if the (straight) lines containing at least threepoints have up to k directions. We present an O(k)-approximation algorithmrunning in n^O(k)-time. Those hardness and approximation results also holds forthe Minimum Convex Tiling problem, defined similarly but allowing the use ofSteiner points. The approximation results are obtained by relating the problemto the Covering Points with Non-Crossing Segments problem. We show that thisproblem is NP-hard, and present an FPT algorithm. This allows us to obtain aconstant-approximation FPT algorithm for the Minimum Convex Partition Problemwhere the parameter is the number of faces.

Hardness and Approximation of Minimum Convex Partition