<p>I'm currently trying to find a reduction to this problem:</p>
<p>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?:</p>
<ol>
<li>Each pair of triangles on the result set can only share 0 or 1 vertex.</li>
<li>If a pair of triangles share 1 vertex they cannot overlap and if they do not share a vertex, they can overlap.</li>
</ol>
<p>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: <a href="https://en.wikipedia.org/wiki/List_of_NP-complete_problems" rel="noreferrer">https://en.wikipedia.org/wiki/List_of_NP-complete_problems</a>, like 3-SAT, 3 dimensional matching, just to name 2.</p>
<ul>
<li>Have someone encounter a similar problem which is NP-complete?</li>
<li>Can it be in another complexity class?</li>
</ul>
<p>Any help or view on
the problem will be much appreciated.
thanks.</p>

CC BY-SA 4.0
2021-01-15T13:43:12.557Z
Maybe I misunderstood the question, but you can test all n over 3 triangles with all others in O(n^6), therefore it is in P...
Avi Tal
CC BY-SA 4.0
2021-01-15T14:29:06.307Z
Is this in the plane or are you allowing larger dimensional spaces?
Lance Fortnow
CC BY-SA 4.0
2021-01-15T17:29:07.143Z
Thanks , I'll clarify is in the plane. And about the question if it is P the thing is that with a set of Points I have nC3 possible triangles, and to find a set of triangles of size k which fulfill these conditions is the time consuming part. It is equivalent to find a independent set in a conflict graph between the triangles, so this problem reduces to independent set but sadly  that doesn't prove its NP completeness, I need to find a problem NP complete which reduces to this triangle problem.
Andres Fuentes
CC BY-SA 4.0
2021-01-15T18:16:06.753Z
I see. So you mean a set of k triangles which all fulfill these conditions simultaneously with all other triangles in the chosen set?
Avi Tal
CC BY-SA 4.0
2021-01-15T18:21:59.887Z
yes that is what I meant to describe.
Andres Fuentes
CC BY-SA 4.0
2021-01-15T19:22:00.360Z
(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?
Neal Young
CC BY-SA 4.0
2021-01-15T19:58:37.247Z
Thank you I edited the problem, yes they must lie in the given set and thanks for the suggestion I'll search about that problem.
Andres Fuentes
CC BY-SA 4.0
2021-01-16T13:30:27.380Z
"They only share 0 or 1 vertex", do you mean pairwise? (each pair independently)
Narek Bojikian
CC BY-SA 4.0
2021-01-16T18:05:55.773Z
Yes pairwise, thanks I edited for clairty
Andres Fuentes
CC BY-SA 4.0
2021-01-16T20:08:23.270Z
"... *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)
Marzio De Biasi
CC BY-SA 4.0
2021-01-17T00:25:56.673Z
1) No, because, points must be in general position so no 3 points are collinear. if the share a vertex, they can´t share anything else.
2) Yes
3) No
Andres Fuentes
<cc.complexity-theory><np-hardness><complexity-classes><cg.comp-geom>
NP complete problem help
Andres Fuentes
# NP complete problem help

(Asked by: username_0 on 2021-01-15)

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.

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, cg.comp-geom
> **Comments:**
> **username_1**: Maybe I misunderstood the question, but you can test all n over 3 triangles with all others in O(n^6), therefore it is in P...  
> **username_2**: Is this in the plane or are you allowing larger dimensional spaces?  
> **username_0**: Thanks , I'll clarify is in the plane. And about the question if it is P the thing is that with a set of Points I have nC3 possible triangles, and to find a set of triangles of size k which fulfill these conditions is the time consuming part. It is equivalent to find a independent set in a conflict graph between the triangles, so this problem reduces to independent set but sadly  that doesn't prove its NP completeness, I need to find a problem NP complete which reduces to this triangle problem.  
> **username_1**: I see. So you mean a set of k triangles which all fulfill these conditions simultaneously with all other triangles in the chosen set?  
> **username_0**: yes that is what I meant to describe.  
> **username_3**: (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?  
> **username_0**: Thank you I edited the problem, yes they must lie in the given set and thanks for the suggestion I'll search about that problem.  
> **username_4**: "They only share 0 or 1 vertex", do you mean pairwise? (each pair independently)  
> **username_0**: Yes pairwise, thanks I edited for clairty  
> **username_5**: "... *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)  
> **username_0**: 1) No, because, points must be in general position so no 3 points are collinear. if the share a vertex, they can´t share anything else. 2) Yes 3) No  

---

## 0 answers

