References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt145",{id:"formSmash:upper:j_idt145",widgetVar:"widget_formSmash_upper_j_idt145",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt146_j_idt148",{id:"formSmash:upper:j_idt146:j_idt148",widgetVar:"widget_formSmash_upper_j_idt146_j_idt148",target:"formSmash:upper:j_idt146:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Evaluation of algorithms for finding bridges between two disjoint convex polygonsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2006 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
##### Abstract [en]

##### Place, publisher, year, edition, pages

2006.
##### Keyword [en]

Technology, Datalogi, Algoritmer för geometriska problem, Broproblemet, Konvexa polygoner
##### Keyword [sv]

Teknik
##### Identifiers

URN: urn:nbn:se:ltu:diva-56282ISRN: LTU-EX--06/025--SELocal ID: d0fa4251-bb72-4f99-949f-93774aae7769OAI: oai:DiVA.org:ltu-56282DiVA: diva2:1029669
##### Subject / course

Student thesis, at least 30 credits
##### Educational program

Computer Science and Engineering, master's level
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt375",{id:"formSmash:j_idt375",widgetVar:"widget_formSmash_j_idt375",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt381",{id:"formSmash:j_idt381",widgetVar:"widget_formSmash_j_idt381",multiple:true});
##### Examiners

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt387",{id:"formSmash:j_idt387",widgetVar:"widget_formSmash_j_idt387",multiple:true});
##### Note

Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

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.

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1088",{id:"formSmash:lower:j_idt1088",widgetVar:"widget_formSmash_lower_j_idt1088",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1089_j_idt1091",{id:"formSmash:lower:j_idt1089:j_idt1091",widgetVar:"widget_formSmash_lower_j_idt1089_j_idt1091",target:"formSmash:lower:j_idt1089:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});