Change search
ReferencesLink to record
Permanent link

Direct link
Evaluation of algorithms for finding bridges between two disjoint convex polygons
2006 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
Keyword [en]
Technology, Datalogi, Algoritmer för geometriska problem, Broproblemet, Konvexa polygoner
Keyword [sv]
URN: urn:nbn:se:ltu:diva-56282ISRN: LTU-EX--06/025--SELocal ID: d0fa4251-bb72-4f99-949f-93774aae7769OAI: diva2:1029669
Subject / course
Student thesis, at least 30 credits
Educational program
Computer Science and Engineering, master's level
Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

Open Access in DiVA

fulltext(313 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 313 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link