Please use this identifier to cite or link to this item:
doi:10.22028/D291-26448
Title: | Constructive Hopf´s theorem : or how to untangle closed planar curves |
Author(s): | Mehlhorn, Kurt Yap, Chee-Keng |
Language: | English |
Year of Publication: | 1988 |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
Abstract: | We consider the classification of polygons (i.e. closed polygonal paths) in which, essentially, two polygons are equivalent if one can be continously transformed into the other without causing two adjacent edges to overlap at some moment. By a theorem of Hopf (for dimension 1, applied to polygons), this amounts to counting the winding number of the polygons. We show that a quadratic number of elementary steps suffices to transform between any two equivalent polygons. Furthermore, this sequence of elementary steps, although quadratic in number, can be described and found in linear time. In order to get our constructions, we give a direct proof of Hopfs result. |
Link to this record: | urn:nbn:de:bsz:291-scidok-51393 hdl:20.500.11880/26504 http://dx.doi.org/10.22028/D291-26448 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 1988/01 |
Date of registration: | 3-Apr-2013 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
fb14_1988_01.pdf | 22,72 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.