I'm a mathematician who got lost here looking for the name of a graph construction. Sorry if my question is silly/out-of-topic, but it seemed like a good place to ask.
I hope my notations are going to be intelligible, but I'm not very aware of the GIS conventions.
My initial problem is to construct a graph from a set of points (s_i)_i=((x_i,y_i))_i which are going to be my vertices. I can thus define the usual Euclidian distance d(s,t) between my vertices.
Now I want to add edges to my graph G=(V,E), so it looks like the road map (which I don't have and want to infer).
I could join each vertex s_i to its k nearest neighbours, but then I won't get the type of connection I want.
My idea is to connect two nodes s,t if there is no other vertex in the graph near the geodesic between s and t. The condition looks like
(s,t) is an edge iff there is no u in V (different from s or t} such that d(s,u) + d(u,t) <= (1+r) d(s,t)
(here r is some positive parameter controlling how close to the geodesic a node can be).
example
If the points are (0,0),(-2,0), (-1,0), (4,0), (0.01,0.5) and (0,1) then
if r = 0
the neighbours of s=(0,0)$ will be {(-1,0),(4,0), (0.01,0.5), (0,1) }$ (but not t=(-2,0) because for u=(-1,0) we have d(s,u) + d(u,t) = (1+r) d(s,t)
if r = 0.1 the neighbours of s=(0,0) will be {(-1,0),(4,0), (0.01,0.5)} (but not t=(0,1) because for u=(0.01,0.5) we have d(s,u) + d(u,t) < (1+r) d(s,t).
I would like to know if such a construction has a name, since I could not find one.
