Look at the convex polygon with n vertices.No four of them lie on the same circle. How many triangles there are with the vertices in polygon's vertices such that remaining n-3 vertices lie outside of the circumcircle of that triangle.I have come so far:Every edge of the polygon belongs to exactly one such triangle(look at the angles which look at that edge from other n-2 vertices, only the biggest angle of n-2 such composes the desired triangle), now the question is how many triangles with the desired property consist of 2 polygonial edges and how many from one and from zero.For n=2014 result is 2012 triangles.
5
- $\begingroup$ Check Delaunay triangulation. $\endgroup$Ante– Ante2014-09-07 18:46:45 +00:00Commented Sep 7, 2014 at 18:46
- $\begingroup$ I can see that it connects. So practically, if there exists such delaunay triangulation for my polygon it leaves me n-2 triangles which seems to be the answer to my problem.I see that what I have written above somewhere completes the proof that beside triangles in delunians config there exist no more of such property, so why is that? $\endgroup$mATHADDICT– mATHADDICT2014-09-07 20:00:30 +00:00Commented Sep 7, 2014 at 20:00
- $\begingroup$ DT covers convex hull of points and polygon triangulation has n-2 triangles. In your case polygon is convex and DT is also a polygon triangulation. $\endgroup$Ante– Ante2014-09-08 08:30:31 +00:00Commented Sep 8, 2014 at 8:30
- $\begingroup$ It is very aggravating to have a question deleted just as I am answering it. (This refers to your Newton iteration question.) $\endgroup$copper.hat– copper.hat2015-02-24 17:01:20 +00:00Commented Feb 24, 2015 at 17:01
- $\begingroup$ Sorry.. i made a mistake while calculating something.. $\endgroup$mATHADDICT– mATHADDICT2015-03-03 22:36:16 +00:00Commented Mar 3, 2015 at 22:36
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
1 All nodes and edges of the triangles that have this property form a graph that is :
1) Connected: because every edge of the polygon belongs to a triangle as you pointed out.
2) Planar: No 2 edges can cross over each other because then there would be 2 triangles that overlap. And that's impossible (lemma 1)
Therefore Eulers theorem says that $V-E+F = 2 $ Where $V$ is the number of vertices, $E$ the number of edges and $F$ the number of faces, including the exterior face.
We have also:
3) Every edge that's not a part of the convex polygon has 2 neighbouring triangles.(lemma2)
Therefore all faces but the exterior face $(F-1)$ have 3 edges. The exterior face has $V$ edges. And every edge has 2 neigbouring faces so we have:
$2E = 3(F-1) + V$
Combined with Euler's Theorem this gives: $F = V-1$ but we have to exclude the exterior face, because it is not a valid triangle, so there are $V-2$ triangles that satisfy the special property.
http://en.wikipedia.org/wiki/Euler_characteristic#Planar_graphs
lemma 1: No 2 triangles that satify the given property can overlap i.e. the intesection of their interiors is empty.
Suppose there are two such triangles, consider the 2 circles $A$ and $B$ that go through the points of the triangles. These circles have to overlap because there are points in their intersection. Therefore the circles intersect in two points that define a line $L$ But triangle 1 is on the left of this line, because all of its 3 points are on circle A but outside circle B. Similarly, the second triangle is on the right of the line. Therefore the 2 triangles cannot overlap
lemma 2: I think you can prove this yourself, since it similar to proving that every edge of the convex poligon is in exactly one triangle.
- $\begingroup$ If i am right, lemma 1 and lemma 2 yield that the graph is actually a triangulation so yielding the number n-2, and this Euleristic symbolism is not necessary, but anyway its a good reference, thanks, i haven't heard for the use of v-e+f=2 in planar graphs.In fact, my thoughts in the post are a special case of lemma 1 for which you gave a nice proof(i think i wasn't going to come with that).And the proof of lemma 2:That defined edge is for sure in one such triangle, let it be on left side.By lemma 1 there is exactly one on left side.For the right side pick the one with biggest angle.Ok? $\endgroup$mATHADDICT– mATHADDICT2014-09-08 15:09:51 +00:00Commented Sep 8, 2014 at 15:09