# 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. },

}