✦ LIBER ✦

Transforming Curves on Surfaces

✍ Scribed by Tamal K. Dey; Sumanta Guha

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 332 KB
Volume: 58
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1998.1619

No coin nor oath required. For personal study only.

✦ Synopsis

We describe an optimal algorithm to decide if one closed curve on a triangulated 2-manifold can be continuously transformed to another, i.e., if they are homotopic. Suppose C 1 and C 2 are two closed curves on a surface M of genus g. Further, suppose T is a triangulation of M of size n such that C 1 and C 2 are represented as edge vertex sequences of lengths k 1 and k 2 in T, respectively. Then, our algorithm decides if C 1 and C 2 are homotopic in O(n+k 1 +k 2 ) time and space, provided g{2 if M is orientable, and g{3, 4 if M is nonorientable. This implies as well an optimal algorithm to decide if a closed curve on a surface can be continuously contracted to a point. Except for three low genus cases, our algorithm completes an investigation into the computational complexity of two classical problems for surfaces posed by the mathematician Max Dehn at the beginning of this century. The novelty of our approach is in the application of methods from modern combinatorial group theory.

📜 SIMILAR VOLUMES

Systems of Curves on Surfaces

✍ M. Juvan; A. Malnič; B. Mohar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 532 KB

It is proved that for each compact (bordered) surface 7 and each integer k there is a constant N with the following property: If 1 is a family of pairwise nonhomotopic closed curves on 7 such that any two curves from 1 intersect in at most k points, then 1 contains at most N curves.

Transforming curves into curves with the

Transforming curves into curves with the same shape

✍ Michael V Levine 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 1018 KB

Exceptional curves on Del Pezzo surfaces

✍ Andreas Leopold Knutsen 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB

## Abstract We classify all cases of exceptional curves on Del Pezzo surfaces, which turn out to be the smooth plane curves and some other cases with Clifford dimension 3. Moreover, the property of being exceptional holds for all curves in the complete linear system. We use this study to extend the

Conference on Curves, surfaces, CAGD and

Conference on Curves, surfaces, CAGD and image processing

📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 145 KB

Isoperimetric inequalities on curved sur

Isoperimetric inequalities on curved surfaces

✍ Isaac Chavel; Edgar A Feldman 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 724 KB

C-Bézier Curves and Surfaces

✍ Jiwen Zhang 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 132 KB

Using the same technique as for the C-B-splines, two other forms of C-Bézier curves and a reformed formula for the subdivisions are proposed. With these new forms, C-Bézier curves can unify the processes for both the normal cases, and the limiting case (α → 0) with precise results. Like the C-B-spli