Originator: Aichholzer et al. (presented by Tim LeSaulnier - REGS 2011)
Definitions: A set P of points in the plane is in general position if no three of its points are collinear. An empty triangle in P is a triple of points {x,y,z} whose convex hull does not contain any points in P other than x,y, and z. Define Δ(P) to be the number of empty triangles in P, and let Δ(n) be the minimum value of Δ(P) over all sets of n points in general position in the plane.
When the points in P are 2-colored, we consider a variation in which we count monochromatic empty triangles. Let Δ2(P) to be the minimum number of monochromatic empty triangles over all 2-colorings of the points in P, and let Δ2(n) be the minimum value of Δ2(P) over all sets of n points in general position in the plane.
We also consider an "edge-colored" variant in which pairs of points are colored. This produces an edge-colored Kn in which the vertices are located at points in the plane and the edges are line segments joining these points. In this variant a triple {x,y,z} is monochromatic if the triangle it induces is colored monochromatically. Let Δ2'(P) be the minimum number of monochromatic empty triangles over all 2-edge-colorings of the pairs of points in P, and let Δ2'(n) be the minimum value of Δ2'(P) over all sets of n points in general position in the plane.
Background: The best known upper and lower bounds on Δ(n) appear in Bárány--Füredi [BF] and Bárány--Valtr [BV], respectively: n2-O(n log n) ≤ Δ(n) ≤ 1.62n2. Other arguments yielding quadratic upper bounds appear in [BF,D,KM,V]. Less is known about Δ2(n). Aicholzer et al. [AFFHHU] showed constructively that Δ2(n) ≥ Ω(n5/4). Pach and Tóth [PT] provided an improved algorithm showing that Δ2(n) ≥ Ω(n4/3).
It is easy to prove Δ'2(P) ≤ Δ2(P) ≤ (1/4)Δ(P) for all P, so the bound of Bárány--Valtr [BV] quickly yields Δ'2(n) ≤ Δ2(n) ≤ 0.405n2. Using the point-sets constructed in Bárány-Valtr, Aichholzer et al. [AFFHHU] constructed 2-colored point-sets showing that Δ2(n) ≤ 0.310n2.
Conjecture 1: [AFFHHU, PT] Δ2(n) ≥ Ω(n2).
Problem 2: Improve the bounds on Δ(n) given above.
Problem 3: Determine the rate of growth of Δ2(n).
Problem 4: Find a good lower bound on Δ'2(n).
Problem 5: Find good bounds on the minimum and maximum values of the ratios Δ(P) / Δ2(P) and Δ(P) / Δ'2(P).
References:
[AFFHHU] O. Aichholzer, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl,
C Huemer, J. Urrutia, Empty monochromatic triangles, Computational Geometry 42
(2009), 934-938.
[BF]
I. Bárány, Z. Füredi, Empty simplices in Euclidean space.
Canadian Mathematics Bulletin 30 (1987), 436-445.
[BV] I. Bárány, P. Valtr, Planar point sets with a small
number of empty convex polygons. Studia
Scientiarum Mathematicarum Hungarica 41 (2004), 243-269.
[D] A. Dumitrescu, Planar sets with few empty convex polygons. Studia
Scientiarum Mathematicarum Hungarica 36 (2000), 93-109.
[KM] M. Katchalski, A. Meir, On empty triangles determined by points in the
plane, Acta Math. Hung. 51 (34) (1988), 323-328.
[PT] J. Pach, G. Tóth, Monochromatic empty triangles in two-colored
point sets. Geometry, Games, Graphs and Education: The Joe Malkevitch
Festschrift, COMAP, Bedford, MA (2008), 195-198.
[V] P. Valtr, On the minimum number of empty polygons in planar point sets.
Studia Scientiarum Mathematicarum Hungarica 30 (1995), 155-163.