A NEW SUBGRAPH OF MINIMUM WEIGHT TRIANGULATIONS

In this paper, two sufficient conditions for identifying a subgraph of minimum weight triangulation of a planar point set are presented. The se conditions are based on local geometric properties of an edge to be identified. Unlike the previous known sufficient conditions for ident ifying subgraphs, such as Keil's beta-skeleton and Yang and Xu's doubl e circles, The local geometric requirement in our conditions is not ne cessary symmetric with respect to the edge to be identified. The ident ified subgraph is different from all the known subgraphs including the newly discovered subgraph: so-called the intersection of local-optima l triangulations by Dickerson et al. An O(n(3)) time algorithm for fin ding this subgraph from a set of n points is presented.