Me temo que la condición de cercar el predio la acabas de introducir ahora mismo. Sin esa condición está bastante claro que tu propuesta no funciona ya que si eliminas cualquiera de las aristas de la envoltura convexa sigues teniendo todos los vértices unidos por una red de longitud menor. Pero aún teniendo en cuenta la condición de que debemos incluir en la solución la envoltura convexa, el algoritmo que propones no funciona. Fíjate que en tu enunciado particular podríamos suponer \( BG<EG \), por lo que si en la solución que propones substituimos una arista por la otra la longitud total de la red disminuye manteniéndose todos los vértices unidos.
Efectivamente, tienes razón en que eliminando uno de los lados de la envoltura convexa, obtenemos menor recorrido. Tomo nota. Si no hiciese falta cercar el predio, tu solución es mejor.
En todo caso, me alegra ver que mi mensaje inicial respecto a Delaunay, Voronoy y Envoltura no iba muy descaminado.
No sabía que estábamos ante un problema aún abierto y del que sólo se conocen soluciones aproximadas que utilizan entre otros métodos, como dice Luis que ha visto en revistas especializadas, Delanauy y Voronoy.
Si sustituyes BG por EG cuando este último segmento es menor, ganas ahorro. En cualquier caso, primero haces toda la red de Delaunay (ver figura 1) y luego se hace la supresión de vértices eligiendo cuando hay varios candidatos al más pequeño.
Sería una buena investigación tratar de buscar una solución exacta bien utilizando Delaunay, Voronoy, Envoltura, bien los de Steiner.
Saludos