Search for: All records

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 G1(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 G0(P) of noncrossing spanning trees, where G1(P) is a subgraph of G0(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.