I'm currently trying to find a reduction to this problem:

Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as vertices) which fulfill these conditions?:

  1. Each pair of triangles on the result set can only share 0 or 1 vertex.
  2. If a pair of triangles share 1 vertex they cannot overlap and if they do not share a vertex, they can overlap.

I have the intuition that answering the above question is NP complete, I already tried some reductions with no luck I tried reducing some these problems: https://en.wikipedia.org/wiki/List_of_NP-complete_problems, like 3-SAT, 3 dimensional matching, just to name 2.

  • Have someone encounter a similar problem which is NP-complete?
  • Can it be in another complexity class?

Any help or view on the problem will be much appreciated. thanks.

  • 1
    $\begingroup$ I see. So you mean a set of k triangles which all fulfill these conditions simultaneously with all other triangles in the chosen set? $\endgroup$
    – Avi Tal
    Jan 15 '21 at 18:16
  • 1
    $\begingroup$ (i) Do you intend that the vertices of each triangle must lie in the given set? (This is not explicitly stated.) (ii) Instead of "therefore" in point 2, do you mean "and"? "therefore" does not seem correct as used. (iii) Maybe you can reduce from the following problem (which I think is NP-hard): Given a set S of n points, and a set T of triangles with vertices in S, is their a triangulation of S that uses only triangles in T? $\endgroup$
    – Neal Young
    Jan 15 '21 at 19:22
  • 1
    $\begingroup$ "They only share 0 or 1 vertex", do you mean pairwise? (each pair independently) $\endgroup$ Jan 16 '21 at 13:30
  • 1
    $\begingroup$ Yes pairwise, thanks I edited for clairty $\endgroup$ Jan 16 '21 at 18:05
  • 1
    $\begingroup$ "... they cannot overlap..." 1) can they share a segment of one of their edges? (e.g. $\{ (0,0),(2,0),(1,1)\}$ and $\{(0,0),(1,0),(0,5,-1)$) Furthermore, 2) are allowed pairs of triangles in which the smallest one is completely contained in a bigger one? Or 3) pairs in which they share a vertex, and the smallest one is completely contained in the other? (do you confirm that 1:Yes 2:Yes 3:No) $\endgroup$ Jan 16 '21 at 20:08

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.