Evaluation of algorithms for finding bridges between two disjoint convex polygons

The bridge problem considers k disjoint regions in the plane or space and tries to place k -1 optimal bridges connecting all the regions. The optimal bridges are de ned as line segments that minimize the length of the longest path between any two points on different regions. Only a small subsection of the bridge problem is discussed in this thesis, namely finding an optimal bridge between two disjoint convex polygons in the plane. Algorithms for finding this optimal bridge in O(n) are here compared with two approximation algorithms that both create bridges in O(log n) time. The first approximation algorithm simply finds the shortest possible bridge and will be called the shortest bridge algorithm. The second approximation algorithm creates a bridge on the bisector between the two common tangents including both polygons: it is introduced in this thesis and will here be called the middle bridge algorithm. The idea of this thesis was to first visualize the three algorithms in a nice looking fashion and then establish and prove the properties of them. The goal was to find out how much longer then with the optimal bridge the longest paths could be in the worst case with the approximation algorithms. All three algorithms are implemented in a flexible program visualizing how the different bridges behave. The approximation algorithms are also theoretically analyzed and compared. Time complexities for the approximation algorithms are shown and both comply with the assumed O(log n). Both approximation algorithms where first estimated to be two-approximations: never having a longest path more than twice as long as with an optimal bridge. This is proved to be true with the shortest bridge algorithm and not true with the middle bridge algorithm. An example of polygons where the middle bridge algorithm creates a bridge with a longest path more than double the length compared to with the optimal bridge is given. An attempt to prove that this really is the worst case is given. A large number of automatically generated polygon setups are also tested to give a hint of how the algorithms usually perform. The choice of what algorithms to include in this thesis was made by the supervisor of the author and was part of the original proposal.Validerat; 20101217 (root