Two Equivalent Representations of Bicolored Order Types

n their seminal work on Multidimensional Sorting, Goodman and Pollack introduced the so-called order type, which for each ordered triple of a point set in the plane gives its orientation, clockwise or counterclockwise. This information is sufficient to solve many problems from discrete geometry where properties of point sets do not depend on the exact coordinates of the points but only on their relative positions. Goodman and Pollack showed that an efficient way to store an order type in a matrix λ of quadratic size (w.r.t. the number of points) is to count for every oriented line spanned
by two points of the set how many of the remaining points lie to the left of this line.
We generalize the concept of order types to bicolored point sets (every point has one of two colors). The bicolored order type contains the orientation of each bicolored triple of points, while no information is stored for monochromatic triples. Similar to the uncolored case, we store the number of blue points that are to the left of an oriented line spanned by two red points or by one red and one blue point in λB . Analogously the number of red points is stored in λR.
We show that the equivalence of the information contained in the orientation of all bicolored point triples and the two matrices λB and λR also holds in the colored case. This is remarkable, as in general the bicolored order type does not even contain sufficient information to determine all extreme points (points on the boundary of the convex hull of the point set).