## 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

- [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.

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 |