Computing the Maximum Detour of a Plane Graph in Subquadratic Time
Research output: Working paper › Research
Documents
- 08-07-WULLF-NILSEN
Final published version, 298 KB, PDF document
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 O(n^2) running time. 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.
Original language | English |
---|---|
Place of Publication | København |
Publisher | Department of Computer Science, University of Copenhagen |
Number of pages | 25 |
Publication status | Published - 2008 |
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 9618113