Academic Journals Database
Disseminating quality controlled scientific knowledge

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

Author(s): Christian Wulff-Nilsen

Journal: Journal of Computational Geometry
ISSN 1920-180X

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

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