### Computing the maximum detour of a plane geometric graph in subquadratic time

#### 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*Θ*(*n*^{2}) running time where*n*is the number of vertices. 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.#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v1i1a7

ISSN: 1920-180X