2
$\begingroup$

Basically, when given an Undirected graph, the problem of getting maximum cycles is known.

This case is quite different. The graphs I'm dealing with are made by converting geometric polygons to vertices and edges, so vertices relative position matters, and there are weights on the edges representing the distance between 2 vertices.

The are 2 problems:

  • Problem 1:

    finding the maximum number of polygons that doesn't share area (not overlapping) but can be tangential to each other.

for example: enter image description here as you can see, the the above graph has a maximum of 5 not overlapping cycles:

  1. purple - (a,b,e,x,d,a)
  2. green - (d,x,n,f,k,i,d)
  3. orange - (x,e,f,n,x)
  4. pink - (b,c,g,f,e,b)
  5. red - (f,g,h,m,k,f)

My way of tackling this was:

Given a Graph G = (V,E). randomly pick a vertex v and

(1) execute DFS(v) on it, hoping it will eventually reach v and that would be the one of the cycles.

meanwhile, for every vertex u it encounters, execute (1).

I'm think it's a good way but I hope to find better (neater) solutions from you.

  • Problem 2:

    finding the maximum number of polygons that doesn't share area (not overlapping) but can be tangential to each other, and for each polygon, it's perimeter is bigger than some pre-defined threshold.

For that problem, I can honestly say I have no clue on how to solve it. ;)

I'll be happy learn about solutions for both problem 1 and problem 2

Thanks!

$\endgroup$
  • $\begingroup$ Please ask one question per post. Thus, please ask only about one problem in your post. If you want to ask about two problems, you can post two separate questions. $\endgroup$ – D.W. Feb 22 '18 at 22:15
  • $\begingroup$ Also, what specifically is your question about Problem 1? You show one solution and ask for "better (neater) solutions". Are you asking whether there exists an algorithm with better asymptotic running time? If so, what is the running time of your algorithm? Are you asking for an algorithm that is simpler to implement or more "clever" or something else? $\endgroup$ – D.W. Feb 22 '18 at 22:16
  • $\begingroup$ For problem 1, try looking up the algorithms by Tarjan for finding all elementary cycles in a directed graph. However at the outset let me tell you that this problem has an exponential time solution in the worst case. $\endgroup$ – Sagnik Feb 23 '18 at 4:43
  • $\begingroup$ Problem 2 is just a reduction from problem 1. If you have all the simple non overlapping cycles from the graph, you have all the polygons. All you have to do is choose the proper polygons. However since the number of polygons is exponential in the worst case, it will not help even if you have a constant time or polynomial time reduction from problem 1. $\endgroup$ – Sagnik Feb 23 '18 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.