Polygons from a list of edges

Question

Given N points in a map of edges Map<Point, List<Edge>>, it's possible to get the polygons formed by these edges in O(N log N)?

What I know is that you have to walk all the vertices and get the edges containing that vertex as a starting point. These are edges of a voronoi diagram, and each vertex has, at most, 3 artists containing it. So, in the map, the key is a vertex, and the value is a list where the vertex is the start 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 the map counterclockwise until I get the initial vertex. That is a polygon, then I put it in a list of polygons and keep looking for others. The problem is I do not want to overcome the complexity O(N log N)

Thanks!

Botello

You probably want to ask here cs.stackexchange.com – Tingle

Is there a specific reason this would not be considered a purely graph problem (e.g. you do not want intersecting edges?). Also if you consider an input of n-polygon with list of edges all the possible sides and diagonals, it can easily be observed that the number of possible polygons is not O(N log N) bound, meaning that in such cases the complexity you aim for is not achievable. Are you interested in all polygons, or e.g. polygons with non-intersecting sets of vertices? – Forficate

When you say a map from point to edges. Are you saying that given a point, I get all of the edges that contain that point? Or given a point, I get all of the polygon's edges where that point is a vertex in the polygon? – Juttajutty

That point is the start of the edges in the value; I think I can modelate it as a directed graph – Botello

Can you tell us more about your data? Is the map a bunch of polygons that arent connected or is it a connected graph? – Juttajutty

Based on the recent questions you posted under the same tags, I assume, you are using an incremental algorithm to find the delaunay triangulation of a set of points and then use it to find the voronoi diagram. Am I right to assume this? If yes, you can use some specialised (and well understood) data structures instead of a vertex and edge list to represent the planar tesselations. Then iterating the "faces" given edges is much more efficient. I can share more information on these if this is the case. – Sulphone

@krish yes, I'm using the incremental algorithm to get the Delaunay tessellation and then the voronoi Diagram – Botello

Answer 1

You can loop through the edges and compute the distance from midpoint of the edge to all sites. Then sort the distances in ascending order and for inner voronoi polygons pick the first and the second. For outer polygons pick the first. Basically an edge separate/divide 2 polygons.

It's something O(m log n).

Bolter

I will try to do so; but it can also be convenient to think this problem as a graph to get some algorithm in O(N) or O(N log N) – Botello

Answer 2

If I did find a polynomial solution to this problem I would not post it here because I am fairly certain this is at least NP-Hard. I think your best bet is to do a DFS. You might find this link useful Finding all cycles in undirected graphs.

You might be able to use the below solution if you can formulate your graph as a directed graph. There are 2^E directed graphs (because each edge can be represented in 2 directions). You could pick a random directed graph and use the below solution to find all of the cycles in this graph. You could do this multiple times for different random directed graphs keeping track of all the cycles and until you've reached a satisfactory error bounds.

You can efficiently create a directed graph with a little bit of state (Maybe store a + or - with an edge to note the direction?) And once you do this in O(n) the first time you can randomly flip x << E directions to get a new graph in what will essentially be constant time.

Since you can create subsequent directed graphs in constant time you need to choose the number of times to run the cycle finding algorithm to have it still be polynomial and efficient.

UPDATE - The below only works for directed graphs

Off the top of my head it seems like it's a better idea to think of this as a graph problem. Your map of vertices to edges is a graph representation. Your problem reduces to finding all of the loops in the graph because each cycle will be a polygon. I think "Tarjan's strongly connected components algorithm" will be of use here as it can do this in O(v+e).

You can find more information on the algorithm here https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Juttajutty

My graph is undirected; do you think I could use BFS to get that cycles in O(N)? – Botello

This might be an NP problem. – Juttajutty

So, if I use the tarjan's algorithm I can get all the polygons in O(|V|+|E|) and since there are 2N-5 vertex and 3N-6 edges, O(|V|+|E|)=O(5N-11)=O(N) – Botello

That only works for directed graphs, you have an undirected graph – Juttajutty

do you think I could modelate it as a directed graph? taking some point as a start of some segments, – Botello

There are 2^E directed graphs that can be made from an undirected graph. There is no sure deterministic way to handle but.. There may be a random algorithm that can help you. – Juttajutty

It's not about finding all loops - think about the "super loop" which is the polygon formed from multiple one. – Protest

Thats still a loop though. I think that one is more reminiscent of a hamiltonian cycle though which makes it even scarier – Juttajutty

What I want to know is, is the graph a bunch of polygons that are disconnected or is the entire graph connected and we have to find the polygons in the different paths. If the entire graph is a bunch of disconnected graphs then we have hope. – Juttajutty

@ValentinaRamirez:You can make the graph directed by sorting all vertices anti clockwise. – Bolter

@Phpdevpad You can just replace the current edge with 2 edges i.e. if you see (a,b) you also need to input (b,a). But you still want to think of (a,b) and (b,a) as the same edge in certain scenarios to not traverse the same edge multiple times. – Juttajutty

@CleoR:Symply sorting counterclockwise doesn't make the graph directed? – Bolter

@Phpdevpad It makes it a directed graph but I think it misses out on some directions. There should be twice the number of edges in the directed graphs representation of an undirected graph. – Juttajutty

@CleoR:I am not an expert, but it's not an asymmetric travelsalesman problem!? – Bolter

@Phpdevpad So this question is asking about trying to solve an NP-Hard problem in polynomial time. We need more information about the graph to exploit something for that to be possible. The Asymmetric TS problem is also NP-Hard and so that won't help here. Although that is sort of a subset of this problem in that you need to find all of the paths that lead back to the node you started from. And then do that for each of the nodes. – Juttajutty

@CleoR:It's a voronoi diagram! – Bolter

@Phpdevpad Im not knowledgable enough on this topic. Can you post an answer and provide some links so I can follow along? – Juttajutty

Oh I see it looks like what you get from a KMeans cluster – Juttajutty

Can you still post an answer so I can follow along with your full train of thought? – Juttajutty

@CleoR:I think a graph isn't so useful here. I posted an answer how to find the polygons. Can you check its the space and time complexity? I am not so knowledgeable either. TY. – Bolter