Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26448
Titel: Constructive Hopf´s theorem : or how to untangle closed planar curves
Verfasser: Mehlhorn, Kurt
Yap, Chee-Keng
Sprache: Englisch
Erscheinungsjahr: 1988
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-51393
hdl:20.500.11880/26504
http://dx.doi.org/10.22028/D291-26448
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1988/01
SciDok-Publikation: 3-Apr-2013
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1988_01.pdf22,72 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.