Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Computing the Maximum Detour of a Plane Graph in Subquadratic Time
verfasst von : Christian Wulff-Nilsen
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.