Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees

摘要

Let P be a set of n points in the plane in general position. The order type of P specifies, for every ordered triple, a positive or negative orientation; and the x-type (a.k.a. crossing type) of P specifies, for every unordered 4-tuple, whether they are in convex position. Geometric algorithms on P typically rely on primitives involving the order type or x-type (i.e., triples or 4-tuples). In this paper, we show that the x-type of P can be reconstructed from the compatible exchange graph G_1(P) of noncrossing spanning trees on P. This extends a recent result by Keller and Perles (2016), who proved that the x-type of P can be reconstructed from the exchange graph G_0(P) of noncrossing spanning trees, where G_1(P) is a subgraph of G_0(P). A crucial ingredient of our proof is a structure theorem on the maximal sets of pairwise noncrossing edges (MSNES) between two components of a planar straight-line graph on the point set P.