Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235511] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Klein, R; Knauer, C; Langerman, S; Morin, P; Sharir, M; Soss, M, Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D, Discrete & Computational Geometry, vol. 39 no. 1-3 (2008), pp. 17-37, ISSN 0179-5376 [doi]
    (last updated on 2017/12/17)

    Abstract:
    The detour and spanning ratio of a graph G embedded in d measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe O(nlog∈n) time algorithms for computing the detour and spanning ratio of a planar polygonal path. By generalizing these algorithms, we obtain O(nlog∈2 n)-time algorithms for computing the detour or spanning ratio of planar trees and cycles. Finally, we develop subquadratic algorithms for computing the detour and spanning ratio for paths, cycles, and trees embedded in 3, and show that computing the detour in 3 is at least as hard as Hopcroft's problem. © 2007 Springer Science+Business Media, LLC.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320