On balanced 4-holes in bichromatic point sets

DOI10.1016/J.COMGEO.2014.09.004zbMATH Open1307.52009arXiv1708.01321OpenAlexW1987993020MaRDI QIDQ482334FDOQ482334

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

• Combinatorial Geometry and Graph Theory
• A note on empty balanced tetrahedra in two-colored point sets in \(\mathbb{R}^3\)
• Empty rainbow triangles in \(k\)-colored point sets
• 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)