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 [1], [2]).

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. The applet will start automatically when displaying this webpage.
[Applet cannot be started]
All options and features should be self-explaining but a more detailed description is given in [1].

Literatur:

[1]:Alexander Klein. Effiziente Berechnung einer dilationsminimalen Triangulierung. Diplomarbeit, Universitä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