CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt871",{id:"formSmash:upper:j_idt871",widgetVar:"widget_formSmash_upper_j_idt871",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt872_j_idt875",{id:"formSmash:upper:j_idt872:j_idt875",widgetVar:"widget_formSmash_upper_j_idt872_j_idt875",target:"formSmash:upper:j_idt872:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

The Euclidean traveling salesman problem with neighborhoods and a connecting fencePrimeFaces.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();
}
}
2000 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

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

Luleå: Luleå tekniska universitet, 2000. , p. 271
##### Series

Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 2000:36
##### National Category

Computer Sciences
##### Research subject

Dependable Communication and Computation Systems
##### Identifiers

URN: urn:nbn:se:ltu:diva-26604Local ID: f2ada1f0-7bc9-11db-8824-000ea68e967bOAI: oai:DiVA.org:ltu-26604DiVA, id: diva2:999770
#####

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

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

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

Godkänd; 2000; 20061116 (haneit)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-01-10Bibliographically approved

An important class of problems in robotics deals with the planning of paths. In this thesis, we study this class of problems from an algorithmic point of view by considering cases where we have complete knowledge of the environment and each solution must ensure that a point-sized robot capable of moving continuously and turning arbitrarily accomplishes the following: (1) visits a given set of objects attached to an impenetrable simple polygon in the plane, and (2) travels along a path of minimum length over all the possible paths that visit the objects without crossing the polygon. In its general form, this is The (Euclidean) Traveling Salesman Problem with Neighborhoods and a Connecting Fence. We make several contributions. One is an algorithm that computes a shortest watchman path in a rectilinear polygon in time polynomial in the size of the polygon. Each point in the polygon is visible from some point along the computed path, which is a shortest visiting path for a set of convex polygons, each of which is bounded by a chord in the interior of the polygon. For the special case of computing a shortest watchman route, where the end points of the resulting path must coincide, we give a polynomial-time algorithm for general simple polygons. We also give substantially faster and more practical algorithms for computing provably short approximations, that is watchman paths/routes with lengths guaranteed to be at most a constant times longer than the length of a shortest watchman path/route only. To achieve one of these approximations, we develop a linear-time algorithm for computing a constant factor approximation in the case where the convex polygons are impenetrable. For this problem, which is called the Zookeeper's Problem, we show how an exact solution can be computed in linear time when the number of convex polygons is constant. We also present an application of our results to the computation of both exact and approximate solutions to the problem of computing a shortest visiting route for a set of lines in the plane.

urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1985",{id:"formSmash:j_idt1985",widgetVar:"widget_formSmash_j_idt1985",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt2072",{id:"formSmash:lower:j_idt2072",widgetVar:"widget_formSmash_lower_j_idt2072",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt2073_j_idt2076",{id:"formSmash:lower:j_idt2073:j_idt2076",widgetVar:"widget_formSmash_lower_j_idt2073_j_idt2076",target:"formSmash:lower:j_idt2073:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});