点击次数：

论文类型：期刊论文

发表时间：2011-05-01

发表刊物：COMPUTERS & MATHEMATICS WITH APPLICATIONS

收录刊物：SCIE、EI

卷号：61

期号：10

页面范围：2944-2951

ISSN号：0898-1221

关键字：Computational topology; Fundamental group; Tight orthogonal homotopic basis; (Canonical) polygonal schema; Cut graph

摘要：In this paper, for a closed oriented triangulated surface with genus g, a method with O(g(3) n log n) running time of constructing tight orthogonal homotopic bases is presented, where a tight orthogonal homotopic basis is a homotopic basis with the properties: 1. the elements of this basis are cycles, 2. any two adjacent cycles of this basis have exactly one common point, 3. any two nonadjacent cycles of this basis have no common point, and 4. any cycle of this basis is one of the shortest cycles of its homotopic group. The major difference between orthogonal homotopic bases and the well-known canonical homotopic bases is that all the cycles of a canonical homotopic basis have a common point and there is no other common point between any two cycles of the canonical homotopic basis while any two adjacent cycles of an orthogonal homotopic basis have exactly one common point and there is no common point among any three cycles of this basis. (C) 2011 Elsevier Ltd. All rights reserved.