Open Problem Garden - Monochromatic empty triangles - Comments

Yes indeed. However in this (re: Monochromatic empty triangles)

Anonymous — Fri, 27 Aug 2010 07:18:43 +0200

Yes indeed. However in this types of problems it is generally implied that the statement is for a sufficently large n.

This has a trivial (re: Monochromatic empty triangles)

Anonymous — Sun, 27 Sep 2009 03:50:33 +0200

This has a trivial counterexample for c > 0.

Consider X = {(0,0), (0,1), (1,0)}, colored {red, blue, blue} respectively. There is only one empty triangle in X, and it is not monochromatic. So it has 0 monochromatic empty triangles, and 0 is not > c*(3^2) for c > 0.

Original source and one improvement. (re: Monochromatic empty triangles)

Anonymous — Tue, 12 May 2009 02:46:44 +0200

The conjecture appeared first in "Oswin Aichholzer, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, Clemens Huemer, and Jorge Urrutia. Empty monochromatic triangles. In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG2008), pages 75-78, 2008."

In this paper the authors show that any set of n points in general position has empty monochromatic triangles. You can get this paper from http://cccg.ca/proceedings/2008/paper18.pdf

There is one improvement showing that any set of n points in general position has empty monochromatic triangles in: "J. Pach, G. Toth. Monochromatic empty triangles in two-colored point sets. In: Geometry, Games, Graphs and Education: the Joe Malkevitch Festschrift (S. Garfunkel, R. Nath, eds.), COMAP, Bedford, MA, 2008, 195--198." Get it from: http://www.math.nyu.edu/~pach/publications/emptytriangle102408.pdf

The lower bound has been improved (re: Monochromatic empty triangles)

Anonymous — Fri, 08 May 2009 23:18:45 +0200

The lower bound has been improved to cn^4/3.

J. Pach and G. Toth: Monochromatic empty triangles in two-colored point sets, in: Geometry, Games, Graphs and Education: the Joe Malkevitch Festschrift (S. Garfunkel, R. Nath, eds.), COMAP, Bedford, MA, 2008, 195--198.

Monochromatic empty triangles

mdevos — Wed, 08 Oct 2008 23:54:07 +0200

Author(s):

Subject: Geometry

If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.

Conjecture There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.