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
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 SizeFormat 
fb14_1988_01.pdf22,72 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.