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?:
- Each pair of triangles on the result set can only share 0 or 1 vertex.
- 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.