On balanced 4-holes in bichromatic point sets

DOI10.1016/J.COMGEO.2014.09.004MaRDI QIDQ482334zbMATH OpenOpenAlexFDO

Authors Sergey Bereg, A. Ramírez-Vigueras, J. Urrutia, P. Pérez-Lantero, J. M. Díaz-Báñez, R. Fabila-Monroy, Toshinori Sakai, I. Ventura

Publication date 23 December 2014

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

balanced 4-holesempty \(k\)-gonsred-blue pointsErdős-Szekeres-type problem

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Abstract: Let $S=RcupB$ be a point set in the plane in general position such that each of its elements is colored either red or blue, where $R$ and $B$ denote the points colored red and the points colored blue, respectively. A quadrilateral with vertices in $S$ is called a $4$-hole if its interior is empty of elements of $S$. We say that a $4$-hole of $S$ is balanced if it has $2$ red and $2$ blue points of $S$ as vertices. In this paper, we prove that if $R$ and $B$ contain $n$ points each then $S$ has at least $frac{n}^2-4n12$ balanced $4$-holes, and this bound is tight up to a constant factor. Since there are two-colored point sets with no balanced {em convex} $4$-holes, we further provide a characterization of the two-colored point sets having this type of $4$-holes.

Recommendations

• A note on empty balanced tetrahedra in two-colored point sets in \(\mathbb{R}^3\)
• Large bichromatic point sets admit empty monochromatic 4-gons
• Computing balanced islands in two colored point sets in the plane
• scientific article; zbMATH DE number 1786511
• Bichromatic quadrangulations with Steiner points

Cites work

• scientific article; zbMATH DE number 3649571 (Why is no real title available?)
• scientific article; zbMATH DE number 7662671 (Why is no real title available?)
• Chromatic variants of the Erdős--Szekeres theorem on points in convex position.
• Counting convex polygons in planar point sets
• Empty convex hexagons in planar point sets
• Konvexe Fünfecke in ebenen Punktmengen
• Large bichromatic point sets admit empty monochromatic 4-gons
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Sets with No Empty Convex 7-Gons
• The empty hexagon theorem

Cited in

(6)

• A note on empty balanced tetrahedra in two-colored point sets in \(\mathbb{R}^3\)
• Empty rainbow triangles in \(k\)-colored point sets
• Combinatorial Geometry and Graph Theory
• Geometric systems of unbiased representatives
• On rainbow quadrilaterals in colored point sets
• Discrete geometry on colored point sets in the plane -- a survey

This page was built for publication: On balanced 4-holes in bichromatic point sets

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