by Pan, X, Li, F and Klette, R
Abstract:
Assume that two points p and q are given and a finite ordered set of simple polygons, all in the same plane; the basic version of a touring-A-sequence-of- polygons problem (TPP) is to find a shortest path such that it starts at p, then visits these polygons in the given order, and ends at q. This paper describes four approximation algorithms for unconstrained versions of problems defined by touring an ordered set of polygons. It contributes to an approximate and partial answer to the previously open problem “What is the complexity of the touringpolygons problem for pairwise disjoint, simple and not necessarily convex polygons?” by providing κ(ε)O(n) approximation algorithms for solving this problem, either for given start and end points p and q, or with allowing to have those variable, where n is the total number of vertices of the given k simple and pairwise disjoint polygons; κ(ε) defines the numerical accuracy in dependency of a selected ε > 0.
Reference:
Approximate shortest path algorithms for sequences of pairwise disjoint simple polygons (Pan, X, Li, F and Klette, R), In Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010, 2010.
Bibtex Entry:
@inproceedings{pan2010approximatepolygons,
author = "Pan, X and Li, F and Klette, R",
booktitle = "Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010",
pages = "175--178",
title = "Approximate shortest path algorithms for sequences of pairwise disjoint simple polygons",
year = "2010",
abstract = "Assume that two points p and q are given and a finite ordered set of simple polygons, all in the same plane; the basic version of a touring-A-sequence-of- polygons problem (TPP) is to find a shortest path such that it starts at p, then visits these polygons in the given order, and ends at q. This paper describes four approximation algorithms for unconstrained versions of problems defined by touring an ordered set of polygons. It contributes to an approximate and partial answer to the previously open problem "What is the complexity of the touringpolygons problem for pairwise disjoint, simple and not necessarily convex polygons?" by providing κ(ε)O(n) approximation algorithms for solving this problem, either for given start and end points p and q, or with allowing to have those variable, where n is the total number of vertices of the given k simple and pairwise disjoint polygons; κ(ε) defines the numerical accuracy in dependency of a selected ε > 0.",
language = "eng",
}