Evaluation of algorithms for finding bridges between twodisjoint convex polygons

Abstract: The bridge problem considers k disjoint regions in the plane or space andtries to place k -1 optimal bridges connecting all the regions. The optimalbridges are de ned as line segments that minimize the length of the longestpath between any two points on different regions. Only a small subsection ofthe bridge problem is discussed in this thesis, namely finding an optimalbridge between two disjoint convex polygons in the plane. Algorithms forfinding this optimal bridge in O(n) are here compared with two approximationalgorithms that both create bridges in O(log n) time. The first approximationalgorithm simply finds the shortest possible bridge and will be called theshortest bridge algorithm. The second approximation algorithm creates abridge on the bisector between the two common tangents including bothpolygons: it is introduced in this thesis and will here be called the middlebridge algorithm. The idea of this thesis was to first visualize the threealgorithms in a nice looking fashion and then establish and prove theproperties of them. The goal was to find out how much longer then with theoptimal bridge the longest paths could be in the worst case with theapproximation algorithms. All three algorithms are implemented in a flexibleprogram visualizing how the different bridges behave. The approximationalgorithms are also theoretically analyzed and compared. Time complexitiesfor the approximation algorithms are shown and both comply with the assumedO(log n). Both approximation algorithms where first estimated to betwo-approximations: never having a longest path more than twice as long aswith an optimal bridge. This is proved to be true with the shortest bridgealgorithm and not true with the middle bridge algorithm. An example ofpolygons where the middle bridge algorithm creates a bridge with a longestpath more than double the length compared to with the optimal bridge isgiven. An attempt to prove that this really is the worst case is given. Alarge number of automatically generated polygon setups are also tested togive a hint of how the algorithms usually perform.The choice of what algorithms to include in this thesis was made by thesupervisor of the author and was part of the original proposal.