Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees
Marcos Oropeza  1  , Csaba D. Tóth  1, 2  
1 : California State University, Northridge
2 : Tufts University

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 .


Online user: 1