Chepoi:2008:DCA:1377676.1377687
Summary
Chepoi, V., Dragan, F., Estellon, B., Habib, M. and Vaxès, Y. (2008) Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. In Proceedings of the twenty-fourth annual symposium on Computational geometry. New York, NY, USA. ACM, pages 59-68. ((URL))
Abstract
{$\delta$}-Hyperbolic metric spaces have been defined by M. Gromov via a simple 4-point condition: for any four points {$u,v,w,x$}, the two larger of the sums {$d(u,v)+d(w,x), d(u,w)+d(v,x), d(u,x)+d(v,w)$} differ by at most {$2\delta$}. Given a finite set {$S$} of points of a {$\delta$}-hyperbolic space, we present simple and fast methods for approximating the diameter of {$S$} with an additive error {$2\delta$} and computing an approximate radius and center of a smallest enclosing ball for {$S$} with an additive error {$3\delta$}. These algorithms run in linear time for classical hyperbolic spaces and for {$\delta$}-hyperbolic graphs and networks. Furthermore, we show that for {$\delta$}-hyperbolic graphs {$G=(V,E)$} with uniformly bounded degrees of vertices, the exact center of {$S$} can be computed in linear time {$O(|E|)$}. We also provide a simple construction of distance approximating trees of {$\delta$}-hyperbolic graphs {$G$} on {$n$} vertices with an additive error {$O(\delta\log_2 n)$}. This construction has an additive error comparable with that given by Gromov for {$n$}-point {$\delta$}-hyperbolic spaces, but can be implemented in {$O(|E|)$} time (instead of {$O(n^2)$}). Finally, we establish that several geometrical classes of graphs have bounded hyperbolicity.
Bibtex entry
@INPROCEEDINGS { Chepoi:2008:DCA:1377676.1377687,
AUTHOR = { Chepoi, V. and Dragan, F. and Estellon, B. and Habib, M. and Vaxès, Y. },
TITLE = { Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs },
BOOKTITLE = { Proceedings of the twenty-fourth annual symposium on Computational geometry },
SERIES = { SCG '08 },
YEAR = { 2008 },
ISBN = { 978-1-60558-071-5 },
LOCATION = { College Park, MD, USA },
PAGES = { 59--68 },
NUMPAGES = { 10 },
URL = { http://doi.acm.org/10.1145/1377676.1377687 },
DOI = { http://doi.acm.org/10.1145/1377676.1377687 },
ACMID = { 1377687 },
PUBLISHER = { ACM },
ADDRESS = { New York, NY, USA },
KEYWORDS = { center, delta-hyperbolic space, diameter, radius },
ABSTRACT = { {$\delta$}-Hyperbolic metric spaces have been defined by M. Gromov via a simple 4-point condition: for any four points {$u,v,w,x$}, the two larger of the sums {$d(u,v)+d(w,x), d(u,w)+d(v,x), d(u,x)+d(v,w)$} differ by at most {$2\delta$}. Given a finite set {$S$} of points of a {$\delta$}-hyperbolic space, we present simple and fast methods for approximating the diameter of {$S$} with an additive error {$2\delta$} and computing an approximate radius and center of a smallest enclosing ball for {$S$} with an additive error {$3\delta$}. These algorithms run in linear time for classical hyperbolic spaces and for {$\delta$}-hyperbolic graphs and networks. Furthermore, we show that for {$\delta$}-hyperbolic graphs {$G=(V,E)$} with uniformly bounded degrees of vertices, the exact center of {$S$} can be computed in linear time {$O(|E|)$}. We also provide a simple construction of distance approximating trees of {$\delta$}-hyperbolic graphs {$G$} on {$n$} vertices with an additive error {$O(\delta\log_2 n)$}. This construction has an additive error comparable with that given by Gromov for {$n$}-point {$\delta$}-hyperbolic spaces, but can be implemented in {$O(|E|)$} time (instead of {$O(n^2)$}). Finally, we establish that several geometrical classes of graphs have bounded hyperbolicity. },
}