Geometry Lab: Dilationsminimale Triangulierung

[English] [Sitemap] [Über geometrylab.de]

Dilationsminimale Triangulierung

Introduction

This applet was created during my diploma thesis as an implementation of the researched algorithms. It allows to find the minimum dilation tringulation of a pointset via several algorithms.

Background Information

For two points x,y in V on a graph G=(V,E) the dilation is defined as the ratio between the length of the shortest way between x,y along the edges of G and the air-line distance. In this applet the euclidean metrik is used to measure the distances. The dilation of a graph is definded as the maximum dilation of all his points. So it describes how the graph is well suited for connecting all points with the smallest detour. Given a pointset S there are many possible triangulations, which all may have a different dilation. The picture below shows a screenshot of the applet, with a pointset and one possible triangulation. The edges between the points, that bear the maximum dilation on this triangulation, are marked yellow

Finding the triangulation with the smallest dilation for a pointset is the task of the given applet. Also there may exists multiple triangulations having the minimum dilation. Therefor 2 algorithms are implemented (see references).

[1] The Bitwise-Enumeration algorithm is a result of my diploma thesis, which only enumerates a reduced set of candidates to speed up the enumeration process.
[2] An reverse enumeration algorithm by Bespamyatnikh, which enumerates all triangulations to find the one with the smallest dilation.

The Applet

The applet is separated into several panels which gives you a lot of opportunity to display the results and properties of the recent calculations. With the left mouse button you can set points and delete points with the right mouse button. There are many ways to create a pointset.

First you can create a pointset using the mouse
Also pointset can be created automatically within the edit-panel under certain restrictions.
Load and save poinsets within the edit-panel. Due to the java security restrictions this can only be done, by downloading the zipped package, extract it to a directory of your choice and start it as browser independent application using the start_application.bat in the extraction directoy file.

The applet will start automatically when displaying this webpage. If it doesn't work, download the package below, unzip it and start the application manually with the given start_application.bat.

[Applet cannot be started]

Download the applet as stand-alone-application
All options and features should be self-explaining but a more detailed description is given in [1].

References

[1] Alexander Klein. Effiziente Berechnung einer dilationsminimalen Triangulierung. Diplomarbeit, Universitaät Bonn. 2006. http://web.informatik.uni-bonn.de/I/Lehre/Diplomarbeiten

[2] S. Bespamyatnikh, An efficient algorithm for enumeration of triangulations. Department of Computer Science, University of British Columbia, 201-2366 Main Mall, Vancouver, BC, V6T 1Z4, Canada. Received 2 October 2000; accepted 2 May 2001

- Letzte Änderung 09-02-2009 10:41