12
$\begingroup$

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.

$\endgroup$
11
  • 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 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 at 19:22
  • 1
    $\begingroup$ "They only share 0 or 1 vertex", do you mean pairwise? (each pair independently) $\endgroup$ – narek Bojikian Jan 16 at 13:30
  • 1
    $\begingroup$ Yes pairwise, thanks I edited for clairty $\endgroup$ – Andres Fuentes Jan 16 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$ – Marzio De Biasi Jan 16 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.