New Bounds on The Encoding of Planar Triangulations

DSpace Repository


Dateien:

URI: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-949
http://hdl.handle.net/10900/48082
Dokumentart: Report
Date: 2000
Source: WSI ; 2000 ; 1
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Datenverdichtung , Triangulierung , Algorithmus
Other Keywords:
compression , planar triangulation , algorithms
License: http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en
Show full item record

Abstract:

Kompakte Kodierungen der Nachbarschaftsbeziegungen von ebenen Triangulierungen ist nicht nur in der Graphtheory von Interesse, sondern auch in der Computer Graphik. 1962 bestimmte Tutte die Anzahl der verschiedenen ebenen Triangulierungen. Von den Ergebnissen kann man schliessen dass jede Kodierung der Nachbarschaftsbeziehungen von ebenen Trianulierungen mit drei Randknoten und k Knoten im assymptotischen Limit fuer beliebig grosse k mindestens 3.245k Bits benoetigt. Zur Zeit erlaubt das beste Verfahren, das auf der Kodierung von CRLSE-Edgebreaker Zeichenketten beruht, weniger als 3.67k Bits. In diesem Report verbessern wir dieses Ergebnis auf 3.552k Bits pro vertex. Ausserdem wird eine neue Kodierungsmethode fuer eine andere Technik - die Cut-Border Machine - vorgestellt. Damit kann das bisher nicht linear beschraenkte Verfahren mit 4.92k Bit beschraenkt werden. Zusaetzlich wird eine Datenstruktur beschrieben, die Kodierung und Dekodierung mit der Cut-Border Machine in linearer Zeit ermoeglichen.

This item appears in the following Collection(s)