Name
Abstract | ||
|---|---|---|
Let S=R∪B 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 n2−4n12 balanced 4-holes, and this bound is tight up to a constant factor. Since there are two-colored point sets with no balanced convex 4-holes, we further provide a characterization of the two-colored point sets having this type of 4-holes. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.comgeo.2014.09.004 | Computational Geometry |
Keywords | Field | DocType |
Red–blue points,Erdős–Szekeres-type problem,Empty k-gons | Discrete mathematics,Combinatorics,Colored,General position,Vertex (geometry),Regular polygon,Quadrilateral,Point set,Mathematics | Journal |
Volume | Issue | ISSN |
48 | 3 | 0925-7721 |
Citations | PageRank | References |
1 | 0.35 | 6 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sergey Bereg | 1 | 245 | 40.81 |
| José Miguel Díaz-Báñez | 2 | 193 | 26.65 |
| Ruy Fabila Monroy | 3 | 48 | 16.57 |
| Pablo Pérez-Lantero | 4 | 47 | 17.76 |
| A. Ramírez-Vigueras | 5 | 3 | 1.08 |
| Toshinori Sakai | 6 | 54 | 9.64 |
| Jorge Urrutia | 7 | 1064 | 134.74 |
| Inmaculada Ventura | 8 | 102 | 10.56 |