Computing the Maximum Detour of a Plane Graph in Subquadratic Time
Publikation: Working paper › Forskning
Standard
Computing the Maximum Detour of a Plane Graph in Subquadratic Time. / Wulff-Nilsen, Christian.
København : Department of Computer Science, University of Copenhagen, 2008.Publikation: Working paper › Forskning
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - UNPB
T1 - Computing the Maximum Detour of a Plane Graph in Subquadratic Time
AU - Wulff-Nilsen, Christian
PY - 2008
Y1 - 2008
N2 - Let G be a plane graph where each edge is a line segment. We consider the problem of computing the maximum detour of G, defined as the maximum over all pairs of distinct points p and q of G of the ratio between the distance between p and q in G and the distance |pq|. The fastest known algorithm for this problem has O(n^2) running time. We show how to obtain O(n^{3/2}*(log n)^3) expected running time. We also show that if G has bounded treewidth, its maximum detour can be computed in O(n*(log n)^3) expected time.
AB - Let G be a plane graph where each edge is a line segment. We consider the problem of computing the maximum detour of G, defined as the maximum over all pairs of distinct points p and q of G of the ratio between the distance between p and q in G and the distance |pq|. The fastest known algorithm for this problem has O(n^2) running time. We show how to obtain O(n^{3/2}*(log n)^3) expected running time. We also show that if G has bounded treewidth, its maximum detour can be computed in O(n*(log n)^3) expected time.
M3 - Working paper
BT - Computing the Maximum Detour of a Plane Graph in Subquadratic Time
PB - Department of Computer Science, University of Copenhagen
CY - København
ER -
ID: 9618113