Article ID Journal Published Year Pages File Type
414873 Computational Geometry 2009 5 Pages PDF
Abstract

We consider a variation of a problem stated by Erdös and Guy in 1973 about the number of convex k-gons determined by any set S of n points in the plane. In our setting the points of S are colored and we say that a spanned polygon is monochromatic if all its points are colored with the same color.As a main result we show that any bi-colored set of n points in R2 in general position determines a super-linear number of empty monochromatic triangles, namely Ω(n5/4).

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics