7

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!

Valentina Ramirez
  • 103
  • 8
  • You probably want to ask here http://cs.stackexchange.com – pvg Jan 12 '16 at 22:33
  • 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? – Boris Strandjev Jan 13 '16 at 06:54
  • 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? – CleoR Jan 13 '16 at 10:17
  • That point is the start of the edges in the value; I think I can modelate it as a directed graph – Valentina Ramirez Jan 13 '16 at 10:21
  • Can you tell us more about your data? Is the map a bunch of polygons that arent connected or is it a connected graph? – CleoR Jan 13 '16 at 23:44
  • 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. – hkrish Jan 15 '16 at 12:21
  • @krish yes, I'm using the incremental algorithm to get the Delaunay tessellation and then the voronoi Diagram – Valentina Ramirez Jan 15 '16 at 17:05

2 Answers2

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).

Micromega
  • 12,486
  • 7
  • 35
  • 72
1

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

Community
  • 1
  • 1
CleoR
  • 806
  • 6
  • 18
  • My graph is undirected; do you think I could use BFS to get that cycles in O(N)? – Valentina Ramirez Jan 13 '16 at 09:38
  • This might be an NP problem. – CleoR Jan 13 '16 at 09:44
  • 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) – Valentina Ramirez Jan 13 '16 at 10:17
  • That only works for directed graphs, you have an undirected graph – CleoR Jan 13 '16 at 10:19
  • do you think I could modelate it as a directed graph? taking some point as a start of some segments, – Valentina Ramirez Jan 13 '16 at 10:22
  • 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. – CleoR Jan 13 '16 at 10:26
  • It's not about finding all loops - think about the "super loop" which is the polygon formed from multiple one. – Alexandru Barbarosie Jan 13 '16 at 23:40
  • Thats still a loop though. I think that one is more reminiscent of a hamiltonian cycle though which makes it even scarier – CleoR Jan 13 '16 at 23:41
  • 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. – CleoR Jan 13 '16 at 23:43
  • @ValentinaRamirez:You can make the graph directed by sorting all vertices anti clockwise. – Micromega Jan 14 '16 at 17:32
  • @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. – CleoR Jan 14 '16 at 17:57
  • @CleoR:Symply sorting counterclockwise doesn't make the graph directed? – Micromega Jan 14 '16 at 18:26
  • @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. – CleoR Jan 14 '16 at 18:33
  • @CleoR:I am not an expert, but it's not an asymmetric travelsalesman problem!? – Micromega Jan 14 '16 at 18:41
  • @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. – CleoR Jan 14 '16 at 18:53
  • @CleoR:It's a voronoi diagram! – Micromega Jan 14 '16 at 20:10
  • @Phpdevpad Im not knowledgable enough on this topic. Can you post an answer and provide some links so I can follow along? – CleoR Jan 14 '16 at 20:21
  • Oh I see it looks like what you get from a KMeans cluster – CleoR Jan 14 '16 at 20:22
  • Can you still post an answer so I can follow along with your full train of thought? – CleoR Jan 14 '16 at 20:23
  • @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. – Micromega Jan 14 '16 at 20:38