id: 05500056
dt: a
an: 05500056
au: Wulff-Nilsen, Christian
ti: Computing the maximum detour of a plane graph in subquadratic time.
so: Hong, Seok-Hee (ed.) et al., Algorithms and computation. 19th international
    symposium, ISAAC 2008, Gold Coast, Australia, December 15‒17, 2008.
    Proceedings. Berlin: Springer (ISBN 978-3-540-92181-3/pbk). Lecture
    Notes in Computer Science 5369, 740-751 (2008).
py: 2008
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-540-92182-0_65
ab: Summary: 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 $Θ(n ^{2})$
    running time where $n$ is the number of vertices. We show how to obtain
    $O(n ^{3/2}\log^{3} n)$ expected running time. We also show that if $G$
    has bounded treewidth, its maximum detour can be computed in
    $O(n\log^{3} n)$ expected time.
rv: