A New Subgraph of Minimum Weight Triangulations |
| |
Authors: | Cao An Wang Francis Chin Yin-Feng Xu |
| |
Institution: | (1) Department of Computer Science, Memorial University of Newfoundland, St. John s, NFLD, Canada, A1C 5S7;(2) Department of Computer Science, University of Hong Kong, Hong Kong;(3) The School of Management, Xi an Jiaotong University, Xi an, P.R. China, a710049 |
| |
Abstract: | In this paper, two sufficient conditions for identifying a subgraph ofminimum weight triangulation of a planar point set are presented. Theseconditions are based on local geometric properties of an edge to beidentified. Unlike the previous known sufficient conditions for identifyingsubgraphs, such as Keil s -skeleton and Yang and Xu s double circles, The localgeometric requirement in our conditions is not necessary symmetric withrespect to the edge to be identified. The identified subgraph is differentfrom all the known subgraphs including the newly discovered subgraph:so-called the intersection of local-optimal triangulations by Dickerson etal. An O(n3) time algorithm for finding this subgraph from a set ofn points is presented. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|