by Chen, X, Li, F and Klette, R
Abstract:
Consider a simple polygon P and a point s on the frontier ∂P of P. For any real δ>0 there exists a shortest path ρ inside of P such that s is on the path fi, and for each point p in ∂P, there exists a point q in ρ at Euclidean distance less than or equal δ to p such that the line segment pq is in P. Such an optimum path ρ is called a shortest route for ∂P visibility under δ-visibility that starts at point s on ∂P. We provide an approximation algorithm (which belongs to the class of rubberband algorithms) for finding such a path ρ in O (n 2) run time, where n is the number of vertices of a given simple polygon P. The run time does not depend on δ or on the start point s. © 2012 Binary Information Press.
Reference:
Approximate shortest routes for frontier visibility under limited visibility (Chen, X, Li, F and Klette, R), In Journal of Computational Information Systems, volume 8, 2012.
Bibtex Entry:
@article{chen2012approximatevisibility,
author = "Chen, X and Li, F and Klette, R",
journal = "Journal of Computational Information Systems",
month = "Aug",
pages = "6841--6849",
title = "Approximate shortest routes for frontier visibility under limited visibility",
volume = "8",
year = "2012",
abstract = "Consider a simple polygon P and a point s on the frontier ∂P of P. For any real δ>0 there exists a shortest path ρ inside of P such that s is on the path fi, and for each point p in ∂P, there exists a point q in ρ at Euclidean distance less than or equal δ to p such that the line segment pq is in P. Such an optimum path ρ is called a shortest route for ∂P visibility under δ-visibility that starts at point s on ∂P. We provide an approximation algorithm (which belongs to the class of rubberband algorithms) for finding such a path ρ in O (n 2) run time, where n is the number of vertices of a given simple polygon P. The run time does not depend on δ or on the start point s. © 2012 Binary Information Press.",
issn = "1553-9105",
issue = "16",
keyword = "Approximate shortest routes",
keyword = "Limited visibility",
keyword = "Simple polygon",
language = "eng",
day = "15",
}