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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $S$ be a 2-colored (red and blue) set of $n$ points in the plane. Asubset $I$ of $S$ is an island if there exits a convex set $C$ such that$I=C\cap S$. The discrepancy of an island is the absolute value of the numberof red minus the number of blue points it contains. A convex partition of $S$is a partition of $S$ into islands with pairwise disjoint convex hulls. Thediscrepancy of a convex partition is the discrepancy of its island of minimumdiscrepancy. The coarseness of $S$ is the discrepancy of the convex partitionof $S$ with maximum discrepancy. This concept was recently defined by Bereg etal. [CGTA 2013]. In this paper we study the following problem: Given a set $S$of $n$ points in general position in the plane, how to color each of them (redor blue) such that the resulting 2-colored point set has small coarseness? Weprove that every $n$-point set $S$ can be colored such that its coarseness is$O(n^{1/4}\sqrt{\log n})$. This bound is almost tight since there exist$n$-point sets such that every 2-coloring gives coarseness at least$\Omega(n^{1/4})$. Additionally, we show that there exists an approximationalgorithm for computing the coarseness of a 2-colored point set, whose ratio isbetween $1/128$ and $1/64$, solving an open problem posted by Bereg et al.[CGTA 2013]. All our results consider $k$-separable islands of $S$, for some$k$, which are those resulting from intersecting $S$ with at most $k$halfplanes.

New results on the coarseness of bicolored point sets