Polygons from the list of edges

Question

Given the Npoints on the map of edges Map<Point, List<Edge>>, we can get the polygons formed by these edges in O(N log N)?

I know that you need to go through all the vertices and get the edges containing that vertex as a starting point. These are the edges of the voronoi diagram, and each vertex has no more than 3 artists who contain it. Thus, on the map, the key is the top, and the value is a list where the top is the beginning of the node.

For example:

Points :a,b,c,d,e,f,g

Edges :[a,b]; [a,c]; [a,d], [b,c], [d,e], [e,g], [g,f]

My idea is to iterate over the map counterclockwise until I get the starting vertex. This is a polygon, then I put it on the list of polygons and keep looking for others. The problem is that I do not want to overcome the difficultyO(N log N)

Thanks!

Answer 1

You can move around the edges and calculate the distance from the middle of the edge to all sites. Then sort the distances in ascending order and for the inner crow polygons, select the first and second. For external polygons, select the first. Basically the edge divides / divides 2 polygons.

This is something O (m log n).

Answer 2

If I could find a polynomial solution to this problem, I would not publish it here, because I am sure that it is at least NP-Hard. I find it best to do DFS. You may find this link useful Searching for all loops in undirected graphs .

, , . 2 ^ E ( 2 ). , . , , .

(, + - , ?) O (n), x < < E, , .

, , , .

UPDATE.

, . . , . , " " , O (v + e).

https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm