Hits:

Indexed by:Journal Papers

Date of Publication:2011-05-01

Journal:COMPUTERS & MATHEMATICS WITH APPLICATIONS

Included Journals:SCIE、EI

Volume:61

Issue:10

Page Number:2944-2951

ISSN No.:0898-1221

Key Words:Computational topology; Fundamental group; Tight orthogonal homotopic basis; (Canonical) polygonal schema; Cut graph

Abstract: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.