Original Post
OK, so say I plot a bunch of random points on a plane, then I connect those points as follows: 1. Pick a point X at random 2. Find the nearest point Y that is not X 3. If the edge XY would not cross any other previously found edges and XY (or YX) is not already an edge, add it to the list of edges 4. Else, try again with the next closest point. 5. Stop when there can be no more edges made. So I end up with a map of closed regions. Given this map and the edge list (which can be easily made into an adjacency graph), can someone help me with an algorithm to find all of the indivisible regions and put them into an adjacency graph? The only idea I have so far is the following algorithm: 1. Select an edge at random 2. Perform a depth-first search on the adjacency graph, and add any cycles I find to the region list 3. Repeat for each edge in the graph 4. Take the found regions and match edges to get an adjacency graph of regions. This algorithm doesn't deal with indivisibility, and that's the problem I'm having. How to tell if the cycles i find are the smallest possible. Any suggestions? -Auron