In this paper, we give a short survey on discrete geometry on red and blue points in the plane, most of whose results were obtained in the past decade. We consider balanced subdivision problems, geometric graph problems, graph embedding problems, Gallai-type problems and others. In this paper, we give a short survey on discrete geometry on red and blue points in the plane, most of whose results were obtained in the past decade. We consider two disjoint sets R and B of red points and of blue points in the plane, respectively, such that no three points of R ∪ B lie on the same line. Throughout this paper, R and B always denote the sets mentioned above unless noted otherwise. We begin with some notation and definitions, which will be used throughout this paper. A (directed) line l trisects the plane into three pieces: l, right(l) and lef t(l), where right(l) and lef t(l) denote the open half-planes which are on the right side and on the left side of l, respectively (Figure 1 ). Let r 1 and r 2 be two rays emanating from the same point p. Then we denote by right(r 1 ) ∩ lef t(r 2 ) the open region that is swept by the ray being rotated clockwise around p from r 1 to r 2 (Figure 1 ). The open region lef t(r 1 ) ∩ right(r 2 ) is similarly defined. Then r 1 ∪ r 2 trisects the plane into three pieces: r 1 ∪ r 2 and two open regions right(r 1 ) ∩ lef t(r 2 ) and lef t(r 1 ) ∩ right(r 2 ). If the internal angle ∠r 1 pr 2 = ∠r 1 r 2 of right(r 1 ) ∩ lef t(r 2 ) is less than π, then we call right(r 1 ) ∩ lef t(r 2 ) the wedge defined by r 1 and r 2 , and denote it by wedge(r 1 r 2 ), wedge(r 2 r 1 ), wedge(r 1 pr 2 ) or wedge(r 2 pr 1 ). right ( Given a point p and a line l passing through p, let l * denote the line lying on l and having the opposite direction of l. We define the rays r and r * to be the two rays emanating from p and lying on the line l, while having the direction of l and l * respectively (Figure 1) . Conversely, given a ray r, we can define r * , l and l * . For a set X of points in the plane, let conv(X) denote the convex hull of X, which is the smallest convex set containing X. For convenience, a region in the plane whose boundary consists of straightline segments is called a polygon even if it is an infinite region. For example, Figure 2
For a detailed survey on geometric problems with red-blue points; see REF .
Discrete geometry on red and blue points in the plane -- a survey
IN DISCRETE AND COMPUTATIONAL GEOMETRY, THE GOODMAN-POLLACK FESTSCHRIFT
Mathematics