nearest vertices that dont cross existing path

2017-04-29

An answer to this question on Stack Overflow.

Question

I have given set of edges E and set of vertices V. Each vertice represents point on 2d space(like for example map of cities). Each edge is some path connecting two vertices (undirected graph) being line segement which length is euclidean metric (distance between two points). Given some vertice n how to find all other vertices m such that edge ( from m to n ) does not cross any edge from E. It is assumed any vertice could be connected to any another as long as adding such connecting edge would not cross any edge from given set E. Note that common vertice does not count as crossing. For example for given graph: Graph V={A,B,C,D,F,G,H} E={{B,C},{D,E}} given vertice A; solution B,C,D, H

Answer

Remove the edge from the graph and run a breadth- or depth-first search seeded at n. All reachable vertices m can be reached without needing to traverse the indicated edge.