Academic Journals Database
Disseminating quality controlled scientific knowledge

Computing the Maximum Detour of a Plane Geometric Graph in Subquadratic Time

ADD TO MY LIST
 
Author(s): Christian Wulff-Nilsen

Journal: Journal of Computational Geometry
ISSN 1920-180X

Volume: 1;
Issue: 1;
Start page: 101;
Date: 2010;
Original page

ABSTRACT
Let G be a plane geometric 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 (vertices as well as interior points of edges) p and q of G of the ratio between the distance between p and q in G and the Euclidean distance ||pq||2. The fastest known algorithm for this problem has Θ(n2) running time where n is the number of vertices. We show how to obtain O(n3/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.
RPA Switzerland

RPA Switzerland

Robotic process automation

    

Tango Rapperswil
Tango Rapperswil