### On the stretch factor of convex Delaunay graphs

#### Abstract

Let

*C*be a compact and convex set in the plane that contains the origin in its interior, and let*S*be a finite set of points in the plane. The Delaunay graph DG_{C}(*S*) of*S*is defined to be the dual of the Voronoi diagram of*S*with respect to the convex distance function defined by*C*. We prove that DG_{C}(*S*) is a*t*-spanner for*S*, for some constant*t*that depends only on the shape of the set*C*. Thus, for any two points*p*and*q*in*S*, the graph DG_{C}(*S*) contains a path between*p*and*q*whose Euclidean length is at most*t*times the Euclidean distance between*p*and*q*.#### Full Text:

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

ISSN: 1920-180X