Points wander around the plane and the Delaunay triangulation induced between them changes. Define two Delaunay triangulations to be adjacent if they are induced by two point configurations which differ by only an infinitesimal change in the position of one point. Define two graphs to be adjacent if they are respectively isomorphic to adjacent Delaunay triangulations.
Adjacent graphs will probably differ by a convex quadrilateral of points divided by a diagonal in two different ways.
Not sure what this is useful for. One could explore a space of graphs (maybe for optimization) by only considering transitions of adjacency.
Also, as other possible small changes to a Delaunay graph: a node splitting into two infinitesimally separated nodes, or the reverse; nodes meeting and merging.
Inspired by political districting amidst populations moving, growing, or shrinking.
No comments :
Post a Comment