New results on the coarseness of bicolored point sets

DOI10.1016/J.IPL.2017.02.007zbMATH Open1431.05031arXiv1211.2020OpenAlexW2963577081MaRDI QIDQ522958FDOQ522958

Authors: P. Pérez-Lantero, J. M. Díaz-Báñez, R. Fabila-Monroy, I. Ventura 

Publication date: 20 April 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: Let $S$ be a 2-colored (red and blue) set of $n$ points in the plane. A subset $I$ of $S$ is an island if there exits a convex set $C$ such that $I=CcapS$. The discrepancy of an island is the absolute value of the number of 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. The discrepancy of a convex partition is the discrepancy of its island of minimum discrepancy. The coarseness of $S$ is the discrepancy of the convex partition of $S$ with maximum discrepancy. This concept was recently defined by Bereg et al. [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 (red or blue) such that the resulting 2-colored point set has small coarseness? We prove that every $n$-point set $S$ can be colored such that its coarseness is $O(n^{1/4}sqrtlogn)$. 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 approximation algorithm for computing the coarseness of a 2-colored point set, whose ratio is between $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.

Full work available at URL: https://arxiv.org/abs/1211.2020

Recommendations

• Computing the coarseness with strips or boxes
• On the coarseness of bicolored point sets
• Expected computations on color spanning sets
• scientific article; zbMATH DE number 1830740
• Discrepancy and approximations for bounded VC-dimension
• PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS
• Quasi‐random 2‐ colorings of point sets
• On the discrepancy for boxes and polytopes
• NP-Completeness of Spreading Colored Points
• scientific article; zbMATH DE number 29926

zbMATH Keywords

coarseness2-coloring

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Coloring of graphs and hypergraphs (05C15) Combinatorial geometries and geometric closure systems (51D20)

Cites Work

• Sequences, discrepancies and applications
• Title not available (Why is that?)
• Geometric discrepancy. An illustrated guide
• Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
• Computing optimal islands
• Sequential and parallel algorithms for finding a maximum convex polygon
• Title not available (Why is that?)
• An elementary approach to lower bounds in geometric discrepancy
• Maximum-weight planar boxes in \(O(n^2)\) time (and better)
• Geometric methods in the study of irregularities of distribution
• 10.1162/153244302760200650
• On the coarseness of bicolored point sets
• Covering convex sets with non-overlapping polygons
• On the density and discrepancy of a 2D point set with applications to thermal analysis of VLSI chips

Cited In (4)

• On the coarseness of bicolored point sets
• Discrete geometry on colored point sets in the plane -- a survey
• Computing the coarseness measure of a bicolored point set over guillotine partitions
• Computing the coarseness with strips or boxes

This page was built for publication: New results on the coarseness of bicolored point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q522958)